215. Kth Largest Element in an Array

Question

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.

Thinking:

• Method 1：sort

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

• Method 2: PriorityQueue
  • 使用lambda会明显降低速度。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                return b - a;
            }
        });
        for(int i = 0; i < nums.length; i++)
            pq.add(nums[i]);
        while(--k != 0)
            pq.poll();
        return pq.poll();
    }
}

二刷

1. Write quick sort by myself though the speed is not fast compared with Arrays.sort()

   class Solution {
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums, 0, nums.length - 1);
        return nums[nums.length - k];
    }
    private void quickSort(int[] nums, int low, int high){
        if(low >= high) return;
        int pivot = partition(nums, low, high);
        quickSort(nums, low, pivot - 1);
        quickSort(nums, pivot + 1, high);
    }
    private int partition(int[] nums, int low, int high){
        int i = low, j = high + 1;
        int cmp = nums[low];
        while(true){
            while(nums[++i] <= cmp) if(i == high) break;
            while(nums[--j] > cmp) if(j == low) break;
            if(i >= j) break;
            swap(nums, i, j);
        }
        swap(nums, low, j);
        return j;
    }
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
   }
   

Amazon session

class Solution {
    public int findKthLargest(int[] nums, int k) {
        sort(nums, 0, nums.length - 1);
        return nums[k - 1];
    }
    private void sort(int[] nums, int low, int high){
        if(low >= high) return;
        int i = partition(nums, low, high);
        sort(nums, low, i - 1);
        sort(nums, i + 1, high);
    }
    private int partition(int[] nums, int low, int high){
        int i = low, j = high + 1;
        int pivot = nums[low];
        while(true){
            while(nums[++i] >= pivot) if(i == high) break;
            while(nums[--j] < pivot) if(j == low) break;
            if(i >= j) break;
            swap(nums, i, j);
        }
        swap(nums, low, j);
        return j;
    }
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}