215 Kth Largest Element in an Array

Quick Select 介紹

目的

找出array中第k小的數字。

方法

和quick sort類似，都是先找一個pivot，把比pivot小的放到左邊，把比pivot大的放到右邊，

放完後，如果pivot所在的位置 == k，表示找到了。

如果pivot所在的位置<k，表示k在pivot的右半邊，

如果pivot所在的位置>k，表示k在pivot的左半邊。

程式實作

Main:

這題題目是要找第k『大』的，也就是第(nums.length - k) 小的，

所以用quick select找第(nums.length-k)小的就是答案。

quick select:

把pivot設為nums中的最後一個element。

現在要把nums中的數字分成兩邊：大於pivot在右邊，小於pivot在左邊。

用一個int left指向左邊的最後一個element的下一個，初始值為0。

從nums[start]跑到nums[end]，

若找到比pivot小的數字，就把它放在left所記錄的左邊最後一個element的下一個位置（swap），

跑完之後，把pivot從nums[end]換到中間，就把左右兩邊分好了！

分好之後，看k落在pivot的左邊還是右邊，決定要把左邊還是右邊再丟進quick select。

Java程式碼如下:

public int findKthLargest(int[] nums, int k) {
    if (nums == null || nums.length == 0) return Integer.MAX_VALUE;
    return findKthLargest(nums, 0, nums.length - 1, nums.length - k);
}    

public int findKthLargest(int[] nums, int start, int end, int k) {// quick select: kth smallest
    if (start > end) return Integer.MAX_VALUE;

    int pivot = nums[end];// Take A[end] as the pivot, 
    int left = start;
    for (int i = start; i < end; i++) {
        if (nums[i] <= pivot) // Put numbers < pivot to pivot's left
            swap(nums, left++, i);            
    }
    swap(nums, left, end);// Finally, swap A[end] with A[left]

    if (left == k)// Found kth smallest number
        return nums[left];
    else if (left < k)// Check right part
        return findKthLargest(nums, left + 1, end, k);
    else // Check left part
        return findKthLargest(nums, start, left - 1, k);
} 

void swap(int[] A, int i, int j) {
    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;                
}