优先队列题目：多次求和构造目标数组

文章目录

• 题目
• • 标题和出处
  • 难度
  • 题目描述
  • • 要求
    • 示例
    • 数据范围
• 解法
• • 思路和算法
  • 代码
  • 复杂度分析

题目

标题和出处

标题：多次求和构造目标数组

出处：1354. 多次求和构造目标数组

难度

7 级

题目描述

要求

给你一个由 n \texttt{n} n 个整数组成的数组 target \texttt{target} target。初始数组 arr \texttt{arr} arr 由 n \texttt{n} n 个 1 \texttt{1} 1 组成，你可以执行以下操作：

• 令 x \texttt{x} x 为你的数组中的所有元素之和。
• 选择下标 i \texttt{i} i，满足 0 ≤ i < n \texttt{0} \le \texttt{i} < \texttt{n} 0≤i<n，将 arr \texttt{arr} arr 的下标 i \texttt{i} i 处的值设为 x \texttt{x} x。
• 你可以重复该过程任意次。

如果可以从 arr \texttt{arr} arr 开始构造出目标数组 target \texttt{target} target，返回 true \texttt{true} true，否则返回 false \texttt{false} false。

示例

示例 1：

输入： target   =   [9,3,5] \texttt{target = [9,3,5]} target = [9,3,5]

输出： true \texttt{true} true

解释：从 arr   =   [1,   1,   1] \texttt{arr = [1, 1, 1]} arr = [1, 1, 1] 开始。

[1,   1,   1] \texttt{[1, 1, 1]} [1, 1, 1]，和为 3 \texttt{3} 3，选择下标 1 \texttt{1} 1。

[1,   3,   1] \texttt{[1, 3, 1]} [1, 3, 1]，和为 5 \texttt{5} 5，选择下标 2 \texttt{2} 2。

[1,   3,   5] \texttt{[1, 3, 5]} [1, 3, 5]，和为 9 \texttt{9} 9，选择下标 0 \texttt{0} 0。

[9,   3,   5] \texttt{[9, 3, 5]} [9, 3, 5] 完成。

示例 2：

输入： target   =   [1,1,1,2] \texttt{target = [1,1,1,2]} target = [1,1,1,2]

输出： false \texttt{false} false

解释：不可能从 [1,1,1,1] \texttt{[1,1,1,1]} [1,1,1,1] 出发构造目标数组。

示例 3：

输入： target   =   [8,5] \texttt{target = [8,5]} target = [8,5]

输出： true \texttt{true} true

数据范围

• n = target.length \texttt{n} = \texttt{target.length} n=target.length
• 1 ≤ n ≤ 5 × 10 4 \texttt{1} \le \texttt{n} \le \texttt{5} \times \texttt{10}^\texttt{4} 1≤n≤5×104
• 1 ≤ target[i] ≤ 10 9 \texttt{1} \le \texttt{target[i]} \le \texttt{10}^\texttt{9} 1≤target[i]≤109

解法

思路和算法

这道题最容易想到的思路是从初始数组开始模拟所有的可能性，但是可能性太多，会超出时间限制，因此需要考虑其他思路。

由于初始数组的元素都是 1 1 1，都是正整数，每次操作都是将数组中的一个元素替换成数组中的所有元素之和，因此每次操作的结果都是将数组中的一个元素值增加，且变化后的元素一定是数组中的最大元素。只要找到数组中的最大元素，即可知道在最后一次操作之前的数组中的所有元素之和，从而将数组恢复到最后一次操作之前的状态。

由此可以反向思考，即从目标数组开始，每次计算上一个状态，判断是否可以得到初始数组。

为了能得到数组中的最大元素，可以使用基于大根堆的优先队列存储数组中的所有元素，优先队列的队首元素即为数组中的最大元素。遍历数组 target \textit{target} target，将所有元素加入优先队列，并计算所有元素之和，记为 sum \textit{sum} sum，然后进行反向操作。

将优先队列的队首元素取出，记为 curr \textit{curr} curr，数组中的其他元素之和为 remainSum = sum − curr \textit{remainSum} = \textit{sum} - \textit{curr} remainSum=sum−curr，则在最后一次操作之前，数组中的所有元素之和为 curr \textit{curr} curr，因此 curr \textit{curr} curr 元素的上一个值为 prev = curr − remainSum \textit{prev} = \textit{curr} - \textit{remainSum} prev=curr−remainSum。将 sum \textit{sum} sum 的值减去 curr − prev \textit{curr} - \textit{prev} curr−prev，将 prev \textit{prev} prev 加入优先队列，则 sum \textit{sum} sum 为最后一次操作之前的数组中的所有元素之和，优先队列中的元素为最后一次操作之前的数组中的所有元素。重复上述反向操作，如果能到达初始数组，即数组中的所有元素都是 1 1 1，则返回 true \text{true} true，如果出现数组中的元素小于 1 1 1 的情况，则返回 false \text{false} false。

当数组中的最大元素远大于数组中的其他元素之和时，上述反向操作的做法仍然会超时。注意到当 curr > remainSum \textit{curr} > \textit{remainSum} curr>remainSum 时，数组中的最大元素一定是 curr \textit{curr} curr，且 remainSum \textit{remainSum} remainSum 的值不会变化，因此每次反向操作都会使 curr \textit{curr} curr 的值减少 remainSum \textit{remainSum} remainSum，直到 curr ≤ remainSum \textit{curr} \le \textit{remainSum} curr≤remainSum 时数组中的最大元素才可能不是 curr \textit{curr} curr。因此可以一步计算 prev \textit{prev} prev，令 prev \textit{prev} prev 为 curr \textit{curr} curr 减去若干个 remainSum \textit{remainSum} remainSum 之后的值且满足 1 ≤ prev ≤ remainSum 1 \le \textit{prev} \le \textit{remainSum} 1≤prev≤remainSum，具体计算方法如下：

• 如果 curr   m o d   remainSum = 0 \textit{curr} \bmod \textit{remainSum} = 0 currmodremainSum=0，则 prev = remainSum \textit{prev} = \textit{remainSum} prev=remainSum；
• 如果 curr   m o d   remainSum ≠ 0 \textit{curr} \bmod \textit{remainSum} \ne 0 currmodremainSum=0，则 prev = curr   m o d   remainSum \textit{prev} = \textit{curr} \bmod \textit{remainSum} prev=currmodremainSum。

得到 prev \textit{prev} prev 之后，将 sum \textit{sum} sum 的值减去 curr − prev \textit{curr} - \textit{prev} curr−prev，将 prev \textit{prev} prev 加入优先队列，即达到用 prev \textit{prev} prev 更新 curr \textit{curr} curr 的效果。

上述反向操作的过程必须保证数组中的全部元素都大于 0 0 0。如果在某一步反向操作之后，数组中的全部元素之和等于 n n n，则恢复到初始数组，返回 true \text{true} true。

如果在反向操作的过程中出现 remainSum = 0 \textit{remainSum} = 0 remainSum=0 或者 curr − remainSum < 1 \textit{curr} - \textit{remainSum} < 1 curr−remainSum<1 的情况，则说明反向操作会导致数组中出现小于 1 1 1 的元素，返回 false \text{false} false。

代码

class Solution {
    public boolean isPossible(int[] target) {
        PriorityQueue<Long> pq = new PriorityQueue<Long>(new Comparator<Long>() {
            public int compare(Long num1, Long num2) {
                return num2.compareTo(num1);
            }
        });
        long sum = 0;
        for (int num : target) {
            sum += num;
            pq.offer((long) num);
        }
        int n = target.length;
        while (sum > n) {
            long curr = pq.poll();
            long remainSum = sum - curr;
            if (remainSum == 0 || curr - remainSum < 1) {
                return false;
            }
            long prev = curr % remainSum == 0 ? remainSum : curr % remainSum;
            sum -= curr - prev;
            pq.offer(prev);
        }
        return sum == n;
    }
}
           

复杂度分析

• 时间复杂度： O ( n log ⁡ n × log ⁡ m ) O(n \log n \times \log m) O(nlogn×logm)，其中 n n n 是数组 target \textit{target} target 的长度， m m m 是数组 target \textit{target} target 的最大元素。

  由于每次反向操作都使数组的最大元素至少减少一半，因此数组中的每个元素最多需要 O ( log ⁡ m ) O(\log m) O(logm) 反向操作即可减少到 1 1 1，将 n n n 个元素都减少到 1 1 1 需要的反向操作次数是 O ( n log ⁡ m ) O(n \log m) O(nlogm)。

  由于每次反向操作需要对优先队列进行取出元素和添加元素操作，优先队列中有 n n n 个元素，每次将元素从优先队列中取出和加入优先队列的时间复杂度是 O ( log ⁡ n ) O(\log n) O(logn)，因此总时间复杂度是 O ( n log ⁡ n × log ⁡ m ) O(n \log n \times \log m) O(nlogn×logm)。

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