February 15, 2019

215. Kth Largest Element in an Array

Solution0. Sort

Sort an array first and then return kth element from the end. Time complexity=O(nlogn)

Solution1. Heap

Analysis:
How to find largest k elements from an unsorted array of size n?  
- Make assumptions: What is the relationship between k and n?
- Solution 1: build a max-heap (heapify) and pop out the top k elements. Time complexity = O(n + klog(n))
- Solution 2: build a min-heap of size k. Init heap 'the smallest element first' (O(k)). keep k largest elements in the heap. Time complexity = O(k + (n-k)log(k))

Java：

Time = O(nlogk), Space = O(k)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        
        // keep k largest elements in the heap
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.poll();
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);

        // PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>(){
        //     @Override
        //     public int compare(Integer o1, Integer o2) {
        //         return o1.compareTo(o2);
        //     }
        // });
        
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        
        return minHeap.poll();
    }
}

Python:

参考 Python doc heapq 的操作：https://docs.python.org/3/library/heapq.html

class Solution:
    def findKthLargest(self, nums: 'List[int]', k: 'int') -> 'int':
        return heapq.nlargest(k, nums)[-1]

Solution2. Quick Select

TODO