1046. Last Stone Weight

題目
最直覺的作法就是先排序，取出最重的兩個撞擊後，把剩下的放回去，然後重複以上步驟：

Intuitive Python 3 solution

def lastStoneWeight(self, stones: List[int]) -> int:
    while len(stones) > 1:
        stones.sort()
        s1 = stones.pop()
        s2 = stones.pop()
        if s1 != s2:
            stones.append(s1 - s2)
    return stones[0] if stones else 0

但這樣的時間複雜度為 O(n^2 * log n)，太大了，有沒有其他方法？

思路：

上面的時間複雜度會大，主因是每次都要花 O(n*log n) 重新排序，有沒有資料結構可以在新增資料的時候小成本的維護大小順序？
答案是 heap，而 Python 有 heapq 這個 implement heap 的 module 可用

Improved Python 3 solution

import heapq


def lastStoneWeight(self, stones: List[int]) -> int:
    stones = [-stone for stone in stones]  # 將 stones 轉換為負數，使其成為最大堆（Max Heap）
    heapq.heapify(stones)  # In-place transform the list to min heap.
    while len(stones) > 1:
        s1 = heapq.heappop(stones)
        s2 = heapq.heappop(stones)
        if s1 != s2:
            heapq.heappush(stones, s1 - s2)  # 第二個參數為小的減大的，因為要放負數進去
    return -stones[0] if stones else 0

時間複雜度分析：
迴圈外：line 5, 6 都是 O(n)
迴圈內：因為 heapq.heappop 和 heapq.heappush 的時間複雜度為 O(log n)，所以迴圈內的複雜度為 O(log n)
迴圈條件：len(stones) 時間複雜度為 O(1)
迴圈執行次數：最差的情況為每次都 push 東西進去，也就是整體上每次都 pop 一個出來，會執行 n - 1 次
=> 綜合以上，時間複雜度為 O(n log n)

# array, heap

1046. Last Stone Weight

評論

分類

標籤雲

最新文章

彙整

標籤

最新文章

彙整

標籤

Your browser is out-of-date!