leetcode練習——排序和搜尋（前 K 個高頻元素）

給你一個整數數組 nums 和一個整數 k ，請你傳回其中出現頻率前 k 高的元素。你可以按 任意順序 傳回答案。

提示：

1 <= nums.length <= 105

k 的取值範圍是 [1, 數組中不相同的元素的個數]

題目資料保證答案唯一，換句話說，數組中前 k 個高頻元素的集合是唯一的

進階：你所設計算法的時間複雜度 必須 優于 O(n log n) ，其中 n 是數組大小。

解法一：https://leetcode-cn.com/problems/top-k-frequent-elements/solution/python-dui-pai-xu-by-xxinjiee/

（36ms/17.8MB）

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        def sift_down(arr, root, k):
            """下沉log(k),如果新的根節點>子節點就一直下沉"""
            val = arr[root] # 用類似插入排序的指派交換
            while root<<1 < k:
                child = root << 1
                # 選取左右孩子中小的與父節點交換
                if child|1 < k and arr[child|1][1] < arr[child][1]:
                    child |= 1
                # 如果子節點<新節點,交換,如果已經有序break
                if arr[child][1] < val[1]:
                    arr[root] = arr[child]
                    root = child
                else:
                    break
            arr[root] = val

        def sift_up(arr, child):
            """上浮log(k),如果新加入的節點<父節點就一直上浮"""
            val = arr[child]
            while child>>1 > 0 and val[1] < arr[child>>1][1]:
                arr[child] = arr[child>>1]
                child >>= 1
            arr[child] = val

        stat = collections.Counter(nums)
        stat = list(stat.items())
        heap = [(0,0)]

        # 建構規模為k+1的堆,新元素加入堆尾,上浮
        for i in range(k):
            heap.append(stat[i])
            sift_up(heap, len(heap)-1) 
        # 維護規模為k+1的堆,如果新元素大于堆頂,入堆,并下沉
        for i in range(k, len(stat)):
            if stat[i][1] > heap[1][1]:
                heap[1] = stat[i]
                sift_down(heap, 1, k+1) 
        return [item[0] for item in heap[1:]]
           

力扣 (LeetCode)連結：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvzpxi/