1675.Minimize Deviation in Array

tags: Hard,Array,Greedy,Heap

1675. Minimize Deviation in Array

題目描述

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

Constraints:

• n == nums.length
• 2 <= n <= 5 * 10⁴
• 1 <= nums[i] <= 10⁹

解答

C++

思路:

1. 奇數只能*2, 偶數只能/2, 找經過操作後最小的deviation
2. 因為奇數做2後, 必定成為偶數且接下來只能/2, 故可以把當前奇數都2後, 以當前數列全為偶數做思考
3. 根據題目我們其實也只關心最大跟最小值的差值, 所以可以紀錄最小值後, 開始把最大值提出來/2, 看不可以縮小差距, 可以的話持續迭代, 直到最大值是奇數不能再/2結束

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        int min_v = INT_MAX, res = INT_MAX;
        priority_queue<int> q;
        for(int i = 0; i < nums.size(); i++)
        {
            nums[i] = nums[i]&1 ? nums[i]*2 : nums[i];
            min_v = min(min_v, nums[i]);
            q.push(nums[i]);
        }
        
        res = q.top() - min_v;
        while(q.top() % 2 == 0)
        {
            int v = q.top()/2; q.pop();
            q.push(v);
            min_v = min(min_v, v);
            res = min(res, q.top()-min_v);
        }
        return res;
    }
};

Time:

$O(nlog(n))$ 最多做n次, 每次push一個值進priority queue
Extra Space:

$O(n)$

XD Feb 24, 2023

方法1

跟天宇一樣，但考慮到數字是

$2^d$的倍數的話，那時間複雜度其實是

$O(nd\log n)$
Runtime 602ms (Beats 38.66%)

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        int lower = INT_MAX;
        priority_queue<int> pq;
        for (int i = 0; i < nums.size(); i++) {
            nums[i] <<= nums[i] & 1;
            lower = min(lower, nums[i]);
            pq.push(nums[i]);
        }
        int ans = pq.top() - lower;
        while (pq.top() % 2 == 0) {
            int value = pq.top() / 2;
            pq.pop();
            pq.push(value);
            lower = min(lower, value);
            ans = min(ans, pq.top() - lower);
        }
        return ans;
    }
};

Yen-Chi ChenSat, Feb 25, 2023

方法2

利用set來減少相同的數字重複檢查，複雜度一樣是

$O(nd\log n)$，但執行時間能減少接近一半
Runtime 333ms (Beats 89.8%)

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        int lower = INT_MAX;
        set<int> s;
        for (int i = 0; i < nums.size(); i++) {
            nums[i] <<= nums[i] & 1;
            lower = min(lower, nums[i]);
            s.insert(nums[i]);
        }
        int ans = *s.rbegin() - lower;
        while (*s.rbegin() % 2 == 0) {
            int value = *s.rbegin();
            s.erase(value);
            value = value / 2;
            s.insert(value);
            lower = min(lower, value);
            ans = min(ans, *s.rbegin() - lower);
        }
        return ans;
    }
};

Yen-Chi ChenSat, Feb 25, 2023

方法3

• 思路
  1. 從前面的方法中會發現，將每個數字一直除以2之後，最終會停在最大的奇數(max_odd)上。
  2. 那試想一下，最小的deviation發生時，這個數列是否會包含這個max_odd呢？答案是肯定的。證明也很簡單，在不失一般性的情況下，我們先假設max_odd還未出現，仍是
     $2\times$max_odd，我們可以將數列中
     $\ge 2\times$max_odd的所有數字都除以2，這樣整個數列的range就會縮小了，而且此時數列中就會包含max_odd。
  3. 接下來就是想辦法讓數列中的數字盡量維持在max_odd附近就好。
  4. 再加一個小技巧，除以2這個運算需要考慮到一個數字是不是偶數，但如果我們把所有的偶數都先除以2一次，這個在max_odd附近的數列，無論奇偶數都只需要考慮乘2就好。
• 作法
  1. 找出每個數字除2到變為奇數後，找出最大的奇數出來。
  2. 對原始的數列中的數字，奇數不動，偶數的一律都先除以2一次，之後再持續除到不大於max_odd。然後將這個數列排序。
  3. 如圖，嘗試把從前面開始的一段數列乘以2，找出紅線範圍最小的情況。
     
     
     Time:
     $O(nd+n\log n)$
     Space:
     $O(1)$
     
     

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        int max_odd = 1;
        for (auto num : nums) {
            while (num % 2 == 0) num >>= 1;
            max_odd = max(max_odd, num);
        }
        for (auto& num : nums) {
            if (num % 2 == 0) {
                num >>= 1;
                while (num > max_odd) num >>= 1;
            }
        }
        sort(nums.begin(), nums.end());
        int ans = max_odd - nums[0], n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            ans = min(ans, max(max_odd, nums[i] * 2) - min(nums[i+1], nums[0] * 2));
        }
        return ans;
    }
};

Yen-Chi ChenSat, Feb 25, 2023

Javascript

function minimumDeviation(nums) {
  const maxHeap = new MaxHeap();
  let min = Infinity;
  for (const num of nums) {
    if (num % 2 === 1) {
      maxHeap.push(num * 2);
      min = Math.min(min, num * 2);
    } else {
      maxHeap.push(num);
      min = Math.min(min, num);
    }
  }

  let result = maxHeap.top() - min;
  while (maxHeap.top() % 2 === 0) {
    const max = maxHeap.pop();
    min = Math.min(min, max / 2);
    maxHeap.push(max / 2);
    result = Math.min(result, maxHeap.top() - min);
  }

  return result;
}

// Priority Queue
class MaxHeap {
  constructor() {
    this.queue = [];
  }

  push(val) {
    this.queue.push(val);
    this.bubbleUp();
    return this;
  }

  pop() {
    const val = this.queue[0];
    const last = this.queue.pop();
    if (this.queue.length > 0) {
      this.queue[0] = last;
      this.bubbleDown();
    }

    return val;
  }

  top() {
    return this.queue[0];
  }

  bubbleUp() {
    let index = this.queue.length - 1;
    let parentIndex = ~~((index - 1) / 2);
    while (this.queue[index] > this.queue[parentIndex]) {
      [this.queue[index], this.queue[parentIndex]] = [this.queue[parentIndex], this.queue[index]];
      index = parentIndex;
      parentIndex = ~~((index - 1) / 2);
    }

    return this;
  }

  bubbleDown() {
    let index = 0;
    let leftIndex = index * 2 + 1;
    let rightIndex = index * 2 + 2;
    let maxIndex = index;
    while (leftIndex < this.queue.length) {
      if (this.queue[leftIndex] > this.queue[maxIndex]) {
        maxIndex = leftIndex;
      }
      if (rightIndex < this.queue.length && this.queue[rightIndex] > this.queue[maxIndex]) {
        maxIndex = rightIndex;
      }

      if (maxIndex === index) break;

      [this.queue[index], this.queue[maxIndex]] = [this.queue[maxIndex], this.queue[index]];
      index = maxIndex;
      leftIndex = index * 2 + 1;
      rightIndex = index * 2 + 2;
    }

    return this;
  }
}

參考樓上兩位大神的方法1，先寫個max heap練習一下，結果錯了好幾次…
MarsgoatMar 2, 2023

Reference

https://leetcode.com/problems/minimize-deviation-in-array/solutions/3224070/javascript-8-lines-greedy-no-pq-time-o-nlogn-space-o-1-100/
分享一下看到一些很神的做法

回到題目列表