8/20 每日一題(給定一個整數k和nums, 當nums長度在K以上時回傳第K大的元素)

 Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

• KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
• int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

 

Example 1:

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

 

Constraints:

• 1 <= k <= 104
• 0 <= nums.length <= 104
• -104 <= nums[i] <= 104
• -104 <= val <= 104
• At most 104 calls will be made to add.
• It is guaranteed that there will be at least k elements in the array when you search for the kth element.

class KthLargest:

    def __init__(self, k: int, nums: List[int]):

        self.k=k

        self.nums=nums

       

    def add(self, val: int) -> int:

        self.nums.append(val)

        self.nums.sort()#有小到大排序

        if len(self.nums)>=self.k:

            return self.nums[-self.k]

-------------------

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.minHeap, self.k = nums, k
        heapq.heapify(self.minHeap)    

#heapq.heapify(iteralbe_obj)轉換成最小堆,是一種二叉樹結構,其中父節點的值會小於或等於子節點的值,

#最小元素位於根結點

#heapq.heapify()作用是在不創建新的數據結構的情況下,將給定的可迭代物件轉換成最小堆

        while len(self.minHeap) > self.k:
            heapq.heappop(self.minHeap)

#他會彈出首相,也是自目前最小的元素, 這個迴圈用意在於始終保持前K大的元素

    def add(self, val: int) -> int:
        heapq.heappush(self.minHeap, val)

#使用heapq.heappush加入新的值到最小堆中
        if len(self.minHeap) > self.k:

            heapq.heappop(self.minHeap)

#始終保持前K大的長度,這樣最小元素就是大K大
        return self.minHeap[0]

# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

----

方法：參考解答

• 使用 k 的值和一個空數據結構來初始化該類，以存儲迄今為止遇到的 k 個最大元素。
• 當向流中添加新元素時，檢查數據結構的大小是否小於k。
• 如果小於 k，只需將新元素添加到數據結構中即可。
• 如果等於k，則將新元素與數據結構中的最小元素進行比較。
• 如果新元素較大，則刪除最小元素並添加新元素。
• 如果新元素較小，則不要將其添加到數據結構中。
• 返回數據結構中的最小元素，它表示流中第 k 大的元素。

直覺：

• 該問題需要找到數字流中的第 k 個最大元素，這意味著我們需要維護迄今為止看到的 k 個最大元素的集合。
• 通過使用最小堆或優先級隊列等數據結構，我們可以有效地跟踪 k 個最大元素，同時丟棄較小的元素。
• 這個想法是以一種我們可以輕鬆訪問其中最小元素的方式存儲遇到的 k 個最大元素。
• 最初，當我們向流中添加元素時，我們會填充數據結構，直到其大小達到 k。至此，我們有了迄今為止看到的 k 個最大元素，其中最小的元素作為最小堆的根或優先級隊列的頂部。
• 對於每個後續元素，我們將其與數據結構中的最小元素進行比較。如果新元素更大，則它成為 k 個最大元素之一，替換最小元素。否則，它會更小，可以忽略不計。
• 通過始終跟踪 k 個最大元素中的最小元素，我們可以有效地找到任意給定點的第 k 個最大元素。

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.min_heap = []
        for num in nums:
            self.add(num)

    def add(self, val: int) -> int:
        if len(self.min_heap) < self.k:
            heapq.heappush(self.min_heap, val)
        elif val > self.min_heap[0]:
            heapq.heapreplace(self.min_heap, val)
        return self.min_heap[0]