Leetcode-703

Posted on |

703. 数据流中的第K大元素

题目

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

示例:

1
2
3
4
5
6
7
8
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

说明:
你可以假设 nums 的长度≥ k-1 且k ≥ 1。

方法

方法1：堆排序

最小堆排序，最小值在根节点处。
根据输入的列表，创建最小堆（heapq.heapify）。当前任务是找出第K大元素，若当前堆中只有k个元素，则第K大元素就是最小堆的根节点。

题目说明，nums 的长度≥ k-1，就是在加入新元素之前，有两种情况。

  • 根据输入nums，创建最小堆
  • 获取长度小于或者等于k的最小堆
  • 添加新元素，返回最小值
    • 原来self.nums长度刚好为k-1，直接添加新元素val（self.nums长度刚好为k）
    • 原来self.nums长度刚好为k，直接添加新元素val，再删除最小值（self.nums长度刚好为k）
  • 返回最小堆的根节点self.nums[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class KthLargest(object):

    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        self.nums=nums
        self.k=k
        heapq.heapify(self.nums)
        while len(self.nums)>k:
            heapq.heappop(self.nums)


    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        if len(self.nums)<self.k:
            heapq.heappush(self.nums,val)
        else:
            heapq.heappushpop(self.nums,val)
        return self.nums[0]

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

参考资料

Function Effect
heapq.heappush(heap, item) 将item压入到堆数组heap中。如果不进行此步操作，后面的heappop()失效
heapq.heappop(heap) 从堆数组heap中取出最小的值，并返回
heapq.heapify(x) x必须是list，此函数将list变成堆，实时操作。从而能够在任何情况下使用堆的函数
heapq.heappushpop(heap, item) （先入堆，后删除）是heappush(heap,item)和heappop(heap)的联合操作.注意：相当于先操作了heappush(heap,item),然后操作heappop(heap)
heapq.heapreplace(heap, item) （先删除，后入堆）是heappop(heap)和heappush(heap,item)的联合操作。注意，相当于先操作了heappop(heap),然后操作heappush(heap,item)