leetcode 1354. Construct Target Array With Multiple Sums（python）

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第32天，點選檢視活動詳情

描述

You are given an array target of n integers. From a starting array arr consisting of n 1's, you may perform the following procedure :

• let x be the sum of all elements currently in your array.
• choose index i, such that 0 <= i < n and set the value of arr at index i to x.
• You may repeat this procedure as many times as needed.

Return true if it is possible to construct the target array from arr, otherwise, return false.

Example 1:

Input: target = [9,3,5]
Output: true
Explanation: Start with arr = [1, 1, 1] 
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done

Example 2:

Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].

Example 3:

Input: target = [8,5]
Output: true

Note:

n == target.length
1 <= n <= 5 * 10^4
1 <= target[i] <= 10^9

解析

根據題意，給定一個包含 n 個整數的陣列 target 。 從包含 n 個 1 的起始陣列 arr 中，可以執行以下過程：

• 當前陣列中所有元素的總和為 x
• 選擇索引 i ，使得 0 <= i < n 並將索引 i 處的 arr 值設定為 x 。
• 您可以根據需要多次重複此過程。

如果可以從 arr 構造目標陣列，則返回 true ，否則返回 false 。

其實就是模擬倒推整個的 A 能否回到 [1,1,...,1] 的初始狀態，這裡需要注意的是很多邊界條件，還有需要特別注意優化的一步計算過程，因為碰到 [1,100000001] 這類用例肯定會超時，因為計算步驟太多，這裡我們用到取模的操作，如果某個位置是最大的數，但是其在進行好幾次逆操作之後仍然是最大的數，那麼我們就能夠用取模來進行計算的加速。如下的例子，

25，3，5
17，3，5
9，3，5
1，3，5
1，3，1
1，1，1

我們可以直接使用取模直接從第一步跳到第四步，節省很多時間。

時間複雜度為 O(NlogN) ，空間複雜度為 O(N) 。

解答

class Solution(object):
    def isPossible(self, A):
        """
        :type target: List[int]
        :rtype: bool
        """
        total = sum(A)
        target = [-i for i in A]  # heap q預設的是小根堆 這邊加負號就相當於變成了一個大根堆
        heapq.heapify(target)  
        while True:
            max = -heapq.heappop(target)  # 取最大數
            if max == 1:  # 說明此刻 target 裡面全都是 -1 了
                return True
            if 2 * max - total < 1:  # 如果是 [4,2,2] 這種一旦逆操作一次變成 [0,2,2] ，已經不符合題意了，以為出現了小於 1 的數
                return False
            sub = total - max  #  sub 表示除 max 以外所有數字的和
            new = max % sub or sub  # 如果出現[1,1000000001] 極端用例， 因為第二個位置的數字在很多次的次逆操作都是最大的，每次都需要減 sub 所以乾脆直接取模，但同整除的情況下是不能直接 new=0 的 所以會是sub
            total -= max - new  # 更新 total ，從 total 中去掉 max 直接降到 new 的差值
            heapq.heappush(target, -new)

執行結果

71 / 71 test cases passed.
Status: Accepted
Runtime: 259 ms
Memory Usage: 18 MB

原題連結

http://leetcode.com/problems/construct-target-array-with-multiple-sums/

您的支援是我最大的動力