215. Kth Largest Element in an Array

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.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

Solution

  1. heap
  2. quickSelect partition函数: 左边为小于等于nums[lo], 右边为大于nums[lo],防止死循环 第k大即 nums[nums.length - k]
  3. Sort ## Complexity
  4. O(Nlogk) O(k)
  5. O(N) O(1)
  6. O(NlogN) O(1)

    Code

    class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for(Integer i : nums){
            if(heap.size() < k) heap.offer(i);
            else{
                if(heap.peek() < i){
                    heap.poll();
                    heap.offer(i);
                }
            }
        }
        return heap.peek();
    }
    }
    
    class Solution {
    public int findKthLargest(int[] nums, int k) {
        shuffle(nums);
        int p = 0;
        int lo = 0, hi = nums.length - 1;
        while(lo < hi){
            p = partition(lo, hi, nums);
            if(p == nums.length - k) {
                break;
            }else if(p > nums.length - k){
                hi = p - 1;
            }else{
                lo = p + 1;
            }
        }
        return nums[nums.length - k];
    }
    public int partition(int lo, int hi, int[] nums){
        int i = lo + 1;
        int j = hi;
        while(true){
            while( i <= j && nums[i] <= nums[lo]) i++; 
            while( i <= j && nums[j] > nums[lo] ) j--;
            if(i > j) break;
    
            swap(nums, i, j);
        }
        swap(nums, lo, j);
        return j;
    }
    
    public void swap(int[] nums, int i , int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    public void shuffle(int[] a){
        Random random = new Random();
        for(int i = 0; i < a.length; i++){
            int r = random.nextInt(i + 1);
            swap(a, i, r);
        }
    }
    }