python3 解法, 执行用时: 5464 ms, 内存消耗: 24.3 MB, 提交时间: 2023-09-26 20:11:39

from sortedcontainers import SortedList
class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        nums=SortedList(num<<1 if num&1 else num for num in nums)

        ans=nums[-1]-nums[0]
        while not nums[-1]&1:
            nums.add(nums.pop()>>1)
            ans=min(ans, nums[-1]-nums[0])
        
        return ans

python3 解法, 执行用时: 3140 ms, 内存消耗: 71.8 MB, 提交时间: 2023-09-26 20:11:20

class API:
    @classmethod
    def smallestRange(cls, nums: List[List[int]]) -> List[int]:
        rangeLeft, rangeRight = -10**9, 10**9
        maxValue = max(vec[0] for vec in nums)
        priorityQueue = [(vec[0], i, 0) for i, vec in enumerate(nums)]
        heapq.heapify(priorityQueue)

        while True:
            minValue, row, idx = heapq.heappop(priorityQueue)
            if maxValue - minValue < rangeRight - rangeLeft:
                rangeLeft, rangeRight = minValue, maxValue
            if idx == len(nums[row]) - 1:
                break
            maxValue = max(maxValue, nums[row][idx + 1])
            heapq.heappush(priorityQueue, (nums[row][idx + 1], row, idx + 1))
        
        return [rangeLeft, rangeRight]


class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        n = len(nums)
        v = [list() for _ in range(n)]
        for i, num in enumerate(nums):
            if num & 1:
                v[i].extend([num, num * 2])
            else:
                while not nums[i] & 1:
                    v[i].append(nums[i])
                    nums[i] //= 2
                v[i].append(nums[i])
                v[i] = v[i][::-1]
        
        ans = API.smallestRange(v)
        return ans[1] - ans[0]

golang 解法, 执行用时: 176 ms, 内存消耗: 7.5 MB, 提交时间: 2023-09-26 20:09:49

func minimumDeviation(nums []int) int {
    min := math.MaxInt64
    // 奇转偶，记录最小值
    for i := range nums {
        if nums[i] & 1 == 1 {
            nums[i] = nums[i] << 1
        }
        if nums[i] < min {
            min = nums[i]
        }
    }
    // 构建最大堆
    for i := (len(nums) - 1) / 2; i >= 0; i-- {
        sink(nums, i, len(nums) - 1)
    }
    // 偏移量为最大值减最小值
    res := nums[0] - min
    
    // 反复缩小最大值，并更新最小值，并将缩小后的值推入堆中
    // 终止条件为当前最大值为奇数（因为奇数不能缩小了）
    for len(nums) > 0 && nums[0] & 1 == 0 {
        // 最大值缩小，并记录最小值
        tmp := nums[0] >> 1
        if tmp < min {
            min = tmp
        }
        // 将缩小后的值放入最大堆中
        nums[0] = tmp
        sink(nums, 0, len(nums) - 1)
        // 计算当前偏移量：最大值减最小值
        if nums[0] - min < res {
            res = nums[0] - min
        }
    }
    return res
}

func sink(heap []int, root, end int) {
    for {
        child := root * 2 + 1
        if child > end {
            return
        }
        if child < end && heap[child] <= heap[child + 1] {
            child++
        }
        if heap[root] > heap[child] {
            return
        }
        heap[root], heap[child] = heap[child], heap[root]
        root = child
    }
}

cpp 解法, 执行用时: 440 ms, 内存消耗: 55.7 MB, 提交时间: 2023-09-26 20:09:08

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        priority_queue<int> large;
        int mini = 0x7fffffff;
        for (auto& it : nums) {
            it = (it & 1) ? it << 1 : it;
            large.push(it);
            mini = min(mini,it);
        }
        int ret = large.top() - mini;
        while (!large.empty() && !(large.top() & 1)) {
            int temp = large.top() >> 1;
            large.pop();
            large.push(temp);
            mini = min(temp, mini);
            ret = min(ret, large.top() - mini);
        }
        return ret;
    }
};

cpp 解法, 执行用时: 160 ms, 内存消耗: 53.5 MB, 提交时间: 2023-09-26 20:08:46

class Solution {
public:
    int minimumDeviation1(vector<int>& nums) {
        int p_max = 1;
        for(int a : nums){
            while(a % 2 == 0) a /= 2;
            p_max = max(p_max, a);
        }
        vector<int> upper;
        int min = p_max;
        for(int a : nums){
            if(a % 2 == 1) a *= 2;
            while(a >= 2 * p_max) a /= 2;
            if(a >= p_max) upper.push_back(a);
            min = std::min(min, a);
        }
        sort(upper.begin(), upper.end());
        int ans = upper.back() - min;
        for(int i = upper.size() - 1; upper[i] > p_max; i -= 1){
            min = std::min(min, upper[i] / 2);
            ans = std::min(ans, upper[i - 1] - min);
        }
        return ans;
    }

    // 位元算优化
    int minimumDeviation(vector<int>& nums) {
        int p_max = 1;
        for(int a : nums) p_max = max(p_max, a >> (__builtin_ctz(a)));
        vector<int> upper;
        int min = p_max;
        for(int a : nums){
            if(a & 1) a <<= 1;
            if(a >= p_max){
                a >>= __builtin_clz(p_max) - __builtin_clz(a);
                if(a < p_max) a <<= 1;
                upper.push_back(a);
            }
            min = std::min(min, a);
        }
        sort(upper.begin(), upper.end());
        int ans = upper.back() - min;
        for(int i = upper.size() - 1; upper[i] > p_max; i -= 1){
            min = std::min(min, upper[i] >> 1);
            ans = std::min(ans, upper[i - 1] - min);
        }
        return ans;
    }
};

java 解法, 执行用时: 108 ms, 内存消耗: 52.6 MB, 提交时间: 2023-09-26 20:07:59

class Solution {
    // 有序集合/优先队列 循环处理
    public int minimumDeviation(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int num : nums) {
            set.add(num % 2 == 0 ? num : num * 2);
        }
        int res = set.last() - set.first();
        while (res > 0 && set.last() % 2 == 0) {
            int max = set.last();
            set.remove(max);
            set.add(max / 2);
            res = Math.min(res, set.last() - set.first());
        }
        return res;
    }
}