Question

Formatted question description: https://leetcode.ca/all/1675.html

You are given an array nums of n positive integers.

You can perform two types of operations on any element of the array any number of times:

If the element is even, divide it by 2. For example, if the array is [1,2,3,4], then you can do this operation on the last element, and the array will be [1,2,3,2]. If the element is odd, multiply it by 2. For example, if the array is [1,2,3,4], then you can do this operation on the first element, and the array will be [2,2,3,4]. The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some number of operations.

Example 1:

Input: nums = [1,2,3,4] Output: 1 Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1. Example 2:

Input: nums = [4,1,5,20,3] Output: 3 Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3. Example 3:

Input: nums = [2,10,8] Output: 3

Algorithm

对于题目描述的修改规则来进行细致分析，对于一个奇数，它只能被修改成其2倍；对于一个偶数，可以一直除以2直到其变为奇数，那么意味着对于每一个数字修改完后的数字个数是有限的，不会超过lognums[i] 个，并且发现可以有办法让这些数字有序，于是问题转化成，对于每个数字维护一个单增的序列，这个序列包含了其所有可能变形的数字，我们的目标是从这样的n个序列里面，每个序列挑选一个数字，让差值最小，这就是LeetCode 632的原题。

所以按照这个思路，用一个二维数组seq维护对于原nums中数字可能变形的结果，从每个序列挑选一个数字，每个序列还是单增的，不禁让人联想到合并K个有序链表，用优先级队列来进行优化。优先级队列里存储的是序列的编号，next数组存储的是其已经访问到seq[i]的第几个数字，maxVal,minVal维护的是局部最大值和局部最小值（也就是目前从每个序列里各选出一个数字，这些数字里面的最大值和最小值），reaMax, resMin维护的则是全局最大值和最小值。

Code

C++

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        vector<vector<int>> seq(n);
        for (int i = 0; i < n; ++i) {
            if (nums[i] & 1) {
                seq[i].emplace_back(nums[i]);
                seq[i].emplace_back(nums[i] * 2);
            }
            else {
                while (!(nums[i] & 1)) {
                    seq[i].emplace_back(nums[i]);
                    nums[i] >>= 1;
                }
                seq[i].emplace_back(nums[i]);
                reverse(seq[i].begin(), seq[i].end());
            }
        }

        vector<int> next(n, 0);
        auto cmp = [&] (const int & a, const int & b) {
            return seq[a][next[a]] > seq[b][next[b]];
        };

        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        int minVal = INT_MAX, maxVal = INT_MIN, resMax = INT_MAX, resMin = 0;
        for (int i = 0; i < n; ++i) {
            pq.emplace(i);
            maxVal = max(maxVal, seq[i][0]);
        }

        while (!pq.empty()) {
            int pos = pq.top(); pq.pop();
            minVal = seq[pos][next[pos]];

            int gap1 = maxVal - minVal, gap2 = resMax - resMin;
            if (gap1 < gap2 || (gap1 == gap2 && minVal < resMin)) {
                resMin = minVal;
                resMax = maxVal;
            }

            if (next[pos] == (int)seq[pos].size() - 1) break;

            ++next[pos];
            maxVal = max(maxVal, seq[pos][next[pos]]);
            pq.emplace(pos);
        }

        return resMax - resMin;
    }
};

Java

class Solution {
    public int minimumDeviation(int[] nums) {
        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int num : nums) {
            if (num % 2 == 1)
                set.add(num * 2);
            else
                set.add(num);
        }
        int minDeviation = set.last() - set.first();
        while (minDeviation > 0 && set.last() % 2 == 0) {
            int max = set.last();
            set.remove(max);
            set.add(max / 2);
            minDeviation = Math.min(minDeviation, set.last() - set.first());
        }
        return minDeviation;
    }
}

// OJ: https://leetcode.com/problems/minimize-deviation-in-array/
// Time: O(NlogN * logC) where C is the maximum number in A
// Space: O(NlogC)
class Solution {
public:
    int minimumDeviation(vector<int>& A) {
        int N = A.size();
        vector<vector<int>> B(N);
        for (int i = 0; i < N; ++i) {
            int x = A[i];
            B[i].push_back(x);
            if (x % 2 == 0) {
                while (x % 2 == 0) {
                    B[i].push_back(x / 2);
                    x /= 2;
                }
                reverse(begin(B[i]), end(B[i]));
            } else B[i].push_back(2 * x);
        }
        int mx = INT_MIN, ans = INT_MAX;
        vector<int> next(N);
        auto cmp = [&](int a, int b) { return B[a][next[a]] > B[b][next[b]]; };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        for (int i = 0; i < N; ++i) {
            pq.push(i);
            mx = max(mx, B[i][0]);
        }
        while (true) {
            int i = pq.top();
            pq.pop();
            ans = min(ans, mx - B[i][next[i]]);
            if (++next[i] == B[i].size()) break;
            mx = max(mx, B[i][next[i]]);
            pq.push(i);
        }
        return ans;
    }
};

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        h = []
        mi = inf
        for v in nums:
            if v & 1:
                v <<= 1
            h.append(-v)
            mi = min(mi, v)
        heapify(h)
        ans = -h[0] - mi
        while h[0] % 2 == 0:
            x = heappop(h) // 2
            heappush(h, x)
            mi = min(mi, -x)
            ans = min(ans, -h[0] - mi)
        return ans

1675 - Minimize Deviation in Array

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions