优先队列题目：数组的最小偏移量

题目

标题和出处

标题：数组的最小偏移量

出处：1675. 数组的最小偏移量

难度

8 级

题目描述

要求

给你一个由 $\text{n}$ 个正整数组成的数组 $\text{nums}$。

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

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

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

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

示例

示例 1：

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

示例 2：

输入：$\text{nums = [4,1,5,20,3]}$
输出：$\text{3}$
解释：你可以将数组转换为 $\text{[4,2,5,5,3]}$，偏移量是 $\text{5 - 2 = 3}$。

示例 3：

输入：$\text{nums = [2,10,8]}$
输出：$\text{3}$

数据范围

• $\text{n}=\text{nums.length}$
• $\text{2}\le \text{n}\le \text{5}\times {\text{10}}^{\text{4}}$
• $\text{1}\le \text{nums[i]}\le {\text{10}}^{\text{9}}$

解法

思路和算法

为了得到数组的最小偏移量，需要将数组的最大值减小，最小值增大。由于每次操作只能将偶数除以 $2$ 或者将奇数乘以 $2$，有两种操作且可行的操作和元素的奇偶性有关，因此情况非常复杂。如果可以将操作限定在其中的一种，则可以显著简化需要考虑的情况。

首先将数组中的所有奇数都乘以 $2$，使得数组中的所有元素都是偶数，然后只需要考虑将元素除以 $2$ 的操作即可。由于将元素除以 $2$ 的操作一定使元素减小，只有当最大元素减小时，数组的偏移量才可能减小，因此应该每次将最大元素除以 $2$，才可能得到数组的最小偏移量。

数组的偏移量为数组的最大值和最小值之差，因此需要维护数组的最大值和最小值。由于每次需要将最大值除以 $2$，为了快速得到最大值，可以使用基于大根堆的优先队列存储数组中的所有元素，优先队列的队首元素即为数组中的最大元素。最大值的维护可以通过优先队列的队首元素得到，最小值的维护可以通过遍历数组的元素得到，并在每次操作之后更新最小值。

具体做法是，将数组中的每个元素加入优先队列，同时维护最小值（注意此时所有的奇数都已经乘以 $2$，因此优先队列中的所有元素和最小值都是偶数）。将所有元素加入优先队列之后，根据队首元素和最小值计算初始状态的数组的偏移量。当最大元素是偶数时，每一轮循环执行以下操作：

1. 将优先队列的队首元素取出，取出的元素即为最大元素，将最大元素除以 $2$ 作为新的数字加入优先队列；

2. 根据新的数字更新最小值；

3. 更新优先队列之后，新的队首元素为当前的最大值，根据当前的最大值和最小值之差计算数组的偏移量，并更新数组的最小偏移量。

当最大元素变成奇数时，上述循环操作停止，因为此时无法将最大元素除以 $2$，也无法将数组的偏移量减小。在初始状态和每一轮循环中出现的数组的偏移量的最小值即为数组的最小偏移量。

代码

以下代码中，优先队列的创建使用了 lambda 表达式。

class Solution {
    public int minimumDeviation(int[] nums) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        int minNum = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num % 2 != 0) {
                num *= 2;
            }
            pq.offer(num);
            minNum = Math.min(minNum, num);
        }
        int minDeviation = pq.peek() - minNum;
        while (pq.peek() % 2 == 0) {
            int num = pq.poll() / 2;
            pq.offer(num);
            minNum = Math.min(minNum, num);
            minDeviation = Math.min(minDeviation, pq.peek() - minNum);
        }
        return minDeviation;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析

• 时间复杂度：$O(n\log n\times \log m)$，其中 $n$ 是数组 $\text{nums}$ 的长度，$m$ 是数组 $\text{nums}$ 的最大元素。
  由于数组中的最大元素的除以 $2$ 的操作最多可以有 $O(\log m)$ 次，因此数组中的全部元素的除以 $2$ 的操作最多有 $O(n\log m)$ 次。
  由于每次操作需要对优先队列进行取出元素和添加元素操作，优先队列中有 $n$ 个元素，每次将元素从优先队列中取出和加入优先队列的时间复杂度是 $O(\log n)$，因此总时间复杂度是 $O(n\log n\times \log m)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。空间复杂度主要取决于优先队列，优先队列中的元素个数不会超过 $n$。