Question

1675. 数组的最小偏移量

English Version

题目描述

给你一个由 n 个正整数组成的数组 nums 。

你可以对数组的任意元素执行任意次数的两类操作：

• 如果元素是 偶数 ，除以 2
  • 例如，如果数组是 [1,2,3,4] ，那么你可以对最后一个元素执行此操作，使其变成 [1,2,3,2]
• 如果元素是 奇数 ，乘上 2
  • 例如，如果数组是 [1,2,3,4] ，那么你可以对第一个元素执行此操作，使其变成 [2,2,3,4]

数组的 偏移量 是数组中任意两个元素之间的 最大差值 。

返回数组在执行某些操作之后可以拥有的 最小偏移量 。

 

示例 1：

输入：nums = [1,2,3,4]
输出：1
解释：你可以将数组转换为 [1,2,3,2]，然后转换成 [2,2,3,2]，偏移量是 3 - 2 = 1

示例 2：

输入：nums = [4,1,5,20,3]
输出：3
解释：两次操作后，你可以将数组转换为 [4,2,5,5,3]，偏移量是 5 - 2 = 3

示例 3：

输入：nums = [2,10,8]
输出：3

 

提示：

• n == nums.length
• 2 <= n <= 5 * 104
• 1 <= nums[i] <= 109

解法

方法一：贪心 + 优先队列

直观上，为了得到数组的最小偏移量，我们需要将减小数组的最大值，增大数组的最小值。

由于每次可以执行乘、除两种操作：将奇数乘以 $2$；将偶数除以 $2$，情况较为复杂，我们可以将奇数统一乘以 $2$，转成偶数，这样就等价于只有一种除法操作。除法操作只能减少某个数，而只有减少最大值，结果才可能更优。

因此，我们用优先队列（大根堆）维护数组的最大值，每次取出堆顶元素做除法操作，将新值放入堆中，并且更新最小值以及堆顶元素与最小值的差值的最小值。

当堆顶元素为奇数时，操作停止。

时间复杂度 $O(n\log n \times \log m)$。其中 $n$, $m$ 分别是数组 nums 的长度以及数组的最大元素。由于数组中的最大元素除以 $2$ 的操作最多有 $O(\log m)$ 次，因此全部元素除以 $2$ 的操作最多有 $O(n\log m)$ 次。每次弹出、放入堆的操作，时间复杂度为 $O(\log n)$。因此，总的时间复杂度为 $O(n\log n \times \log m)$。

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

class Solution {
  public int minimumDeviation(int[] nums) {
    PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
    int mi = Integer.MAX_VALUE;
    for (int v : nums) {
      if (v % 2 == 1) {
        v <<= 1;
      }
      q.offer(v);
      mi = Math.min(mi, v);
    }
    int ans = q.peek() - mi;
    while (q.peek() % 2 == 0) {
      int x = q.poll() / 2;
      q.offer(x);
      mi = Math.min(mi, x);
      ans = Math.min(ans, q.peek() - mi);
    }
    return ans;
  }
}

class Solution {
public:
  int minimumDeviation(vector<int>& nums) {
    int mi = INT_MAX;
    priority_queue<int> pq;
    for (int v : nums) {
      if (v & 1) v <<= 1;
      pq.push(v);
      mi = min(mi, v);
    }
    int ans = pq.top() - mi;
    while (pq.top() % 2 == 0) {
      int x = pq.top() >> 1;
      pq.pop();
      pq.push(x);
      mi = min(mi, x);
      ans = min(ans, pq.top() - mi);
    }
    return ans;
  }
};

func minimumDeviation(nums []int) int {
  q := hp{}
  mi := math.MaxInt32
  for _, v := range nums {
    if v%2 == 1 {
      v <<= 1
    }
    heap.Push(&q, v)
    mi = min(mi, v)
  }
  ans := q.IntSlice[0] - mi
  for q.IntSlice[0]%2 == 0 {
    x := heap.Pop(&q).(int) >> 1
    heap.Push(&q, x)
    mi = min(mi, x)
    ans = min(ans, q.IntSlice[0]-mi)
  }
  return ans
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
  a := h.IntSlice
  v := a[len(a)-1]
  h.IntSlice = a[:len(a)-1]
  return v
}
func (h *hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }