leetcode-703-Kth-Largest-Element-in-a-Stream

描述

---

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.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

Example:

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

Note:
You may assume that nums‘ length ≥ k-1 and k ≥ 1.

分析

---

用优先队列解决，类似的题目还有 Kth Smallest Element in a Sorted Matrix，Kth Largest Element in an Array。

解决方案1(Java)

---

class KthLargest {
    
    private PriorityQueue<Integer> heap;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        heap = new PriorityQueue<Integer>(k);
        for (int a: nums) {
            add(a);
        }
    }
    
    public int add(int val) {
        heap.offer(val);
        if (heap.size() > k) {
            heap.poll();
        }
        return heap.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

解决方案2（Python）

---

直接使用标准库的堆。

class KthLargest(object):

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

    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        heapq.heappush(self.queue, val)
        while len(self.queue) > self.k:
            heapq.heappop(self.queue)
        return self.queue[0]
        


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

解决方案3（Golang）

---

自己实现一个最小堆。

type KthLargest struct {
    k int
    arr []int
}


func heapify(arr []int, index, size int) {
    left := (index<<1) + 1
    root := index
    right := left+1
    if left < size && arr[left] < arr[root] {
        root = left
    }
    if right < size && arr[right] < arr[root] {
        root = right
    }
    if root != index {
        arr[root], arr[index] = arr[index], arr[root]
        heapify(arr, root, size)
    }
}

func Constructor(k int, nums []int) KthLargest {
    arr := make([]int, k)
    for i := len(nums); i < k; i++ {
        nums = append(nums, -100001)
    }
    for i := 0; i < k; i++ {
        arr[i] = nums[i]
    }
    for i := k>>1; i >= 0; i-- {
        heapify(arr, i, k)
    }
    for i := len(nums)-1; i >= k; i-- {
        if arr[0] < nums[i] {
            arr[0] = nums[i]
            heapify(arr, 0, k)
        }
    }
    return KthLargest{k, arr}
}


func (this *KthLargest) Add(val int) int {
    if val > this.arr[0] {
        this.arr[0] = val
        heapify(this.arr, 0, this.k)
    }
    return this.arr[0]
}


/**
 * Your KthLargest object will be instantiated and called as such:
 * obj := Constructor(k, nums);
 * param_1 := obj.Add(val);
 */

相关问题

---

• (M) Kth Largest Element in an Array

题目来源