leetcode解题: Kth Largest Element in an Array (215)

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

解法1：PriorityQueue, O(NlogK), Space O(K)

一种解法是很直观的用heap来解决，维护一个大小为k的堆。因为每次insert的操作的时间复杂度是O(logK), 一共要遍历N个元素。
最后取出顶元素即可。
Java

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k);
        
        for (int num: nums) {
            queue.offer(num);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        
        return queue.poll();
    }
}

解法2：比较优解 Quick Select, Average O(N), worst O(N^2), Space O(1)

主要是用到了Quick Select中一次partition就可以知道pivot在array中的具体位置，假设是X。
那么如果X == k, 我们要求的就求道了。假设是X < k, 那么我们只需要在右半边找，反之就在左半边找。
要掌握partition函数的写法。
Java

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        if (k <= 0) {
            return 0;
        }
        
        return helper(nums, nums.length - k + 1, 0, nums.length - 1);
        
    }
    
    private int helper(int[] nums, int k, int start, int end) {
        if (start == end) {
            return nums[start];
        }
        
        int p = partition(nums, start, end);
        if (p + 1 == k) {
            return nums[p];
        } else if (p + 1 < k) {
            return helper(nums, k, p + 1, end);
        } else {
            return helper(nums, k, start, p - 1);
        }
    }
    
    private int partition(int[] nums, int start, int end) {
        int pivot = nums[end];
        int index = start;
        for (int i = start; i < end; ++i) {
            if (nums[i] < pivot) {
                swap(nums, index, i);
                ++index;
            }
        }
        swap(nums, end, index);
        return index;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}