代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
给你一个整数数组 target 。一开始，你有一个数组 A ，它的所有元素均为 1 ，你可以执行以下操作：
x 为你数组里所有元素的和0 <= i < target.size 的任意下标 i ，并让 A 数组里下标为 i 处的值为 x 。如果能从 A 开始构造出目标数组 target ，请你返回 True ，否则返回 False 。
示例 1：
输入：target = [9,3,5] 输出：true 解释：从 [1, 1, 1] 开始 [1, 1, 1], 和为 3 ，选择下标 1 [1, 3, 1], 和为 5， 选择下标 2 [1, 3, 5], 和为 9， 选择下标 0 [9, 3, 5] 完成
示例 2：
输入：target = [1,1,1,2] 输出：false 解释：不可能从 [1,1,1,1] 出发构造目标数组。
示例 3：
输入：target = [8,5] 输出：true
提示：
N == target.length1 <= target.length <= 5 * 10^41 <= target[i] <= 10^9我们发现，如果从数组 $arr$ 开始正向构造目标数组 $target$，每次都不好确定选择哪个下标 $i$，问题比较复杂。而如果我们从数组 $target$ 开始逆向构造，每次构造都一定是选择当前数组中最大的元素，这样就可以保证每次构造都是唯一的，问题比较简单。
因此，我们可以使用优先队列（大根堆）来存储数组 $target$ 中的元素，用一个变量 $s$ 记录数组 $target$ 中所有元素的和。每次从优先队列中取出最大的元素 $mx$，计算当前数组中除 $mx$ 以外的所有元素之和 $t$，如果 $t \lt 1$ 或者 $mx - t \lt 1$，则说明无法构造目标数组 $target$，返回 false。否则，我们计算 $mx \bmod t$，如果 $mx \bmod t = 0$，则令 $x = t$，否则令 $x = mx \bmod t$，将 $x$ 加入优先队列中，并更新 $s$ 的值，重复上述操作，直到优先队列中的所有元素都变为 $1$，此时返回 true。
时间复杂度 $O(n \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $target$ 的长度。
class Solution:
def isPossible(self, target: List[int]) -> bool:
s = sum(target)
pq = [-x for x in target]
heapify(pq)
while -pq[0] > 1:
mx = -heappop(pq)
t = s - mx
if t == 0 or mx - t < 1:
return False
x = (mx % t) or t
heappush(pq, -x)
s = s - mx + x
return True
class Solution {
public boolean isPossible(int[] target) {
PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());
long s = 0;
for (int x : target) {
s += x;
pq.offer((long) x);
}
while (pq.peek() > 1) {
long mx = pq.poll();
long t = s - mx;
if (t == 0 || mx - t < 1) {
return false;
}
long x = mx % t;
if (x == 0) {
x = t;
}
pq.offer(x);
s = s - mx + x;
}
return true;
}
}
class Solution {
public:
bool isPossible(vector<int>& target) {
priority_queue<int> pq;
long long s = 0;
for (int i = 0; i < target.size(); i++) {
s += target[i];
pq.push(target[i]);
}
while (pq.top() != 1) {
int mx = pq.top();
pq.pop();
long long t = s - mx;
if (t < 1 || mx - t < 1) {
return false;
}
int x = mx % t;
if (x == 0) {
x = t;
}
pq.push(x);
s = s - mx + x;
}
return true;
}
};
func isPossible(target []int) bool {
pq := &hp{target}
s := 0
for _, x := range target {
s += x
}
heap.Init(pq)
for target[0] > 1 {
mx := target[0]
t := s - mx
if t < 1 || mx-t < 1 {
return false
}
x := mx % t
if x == 0 {
x = t
}
target[0] = x
heap.Fix(pq, 0)
s = s - mx + x
}
return true
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] > h.IntSlice[j] }
func (hp) Pop() (_ any) { return }
func (hp) Push(any) {}
function isPossible(target: number[]): boolean {
const pq = new MaxPriorityQueue();
let s = 0;
for (const x of target) {
s += x;
pq.enqueue(x);
}
while (pq.front().element > 1) {
const mx = pq.dequeue().element;
const t = s - mx;
if (t < 1 || mx - t < 1) {
return false;
}
const x = mx % t || t;
pq.enqueue(x);
s = s - mx + x;
}
return true;
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。