更多代碼和Leetcode題目解析請看這里

什么是Quick select?

• Quick select算法通常用來在未排序的數(shù)組中尋找第k小/第k大的元素。其方法類似于Quick sort。Quick select和Quick sort都是由Tony Hoare發(fā)明的，因此Quick select算法也被稱為是Hoare's selection algorithm。
• Quick select算法因其高效和良好的average case時間復雜度而被廣為應用。Quick select的average case時間復雜度為O(n)，然而其worst case時間復雜度為O(n^2)。
• 總體而言，Quick select采用和Quick sort類似的步驟。首先選定一個pivot，然后根據(jù)每個數(shù)字與該pivot的大小關系將整個數(shù)組分為兩部分。那么與Quick sort不同的是，Quick select只考慮所尋找的目標所在的那一部分子數(shù)組，而非像Quick sort一樣分別再對兩邊進行分割。正是因為如此，Quick select將平均時間復雜度從O(nlogn)降到了O(n)。

Quick select 算法描述

Input: array nums, int k. (find kth smallest element in an unsorted array)
Output: int target

1. Choose an element from the array as pivot, exchange the position of pivot and number at the end of the array.
   • _The pivot can either be the end element or a random chosen element. A random chosen pivot can make the algorithm much possibly run in average case time. _
2. Partition the array into 2 parts in which the numbers in left subarray is less than (or equal to) the pivot and the numbers in right subarray is greater than (or equal to) the pivot.
3. Exchange pivot (at the end of the array now) with the first element in the right part.
4. Compare k with length of the left subarray, say, len.
   • if k == len + 1， then pivot is the target.
   • if k <= len, repeat from step 1 on the left subarray.
   • if k > len, k = k - len, repeat from step 1 on the right subarray.

Quick Select Java實現(xiàn)

Java代碼如下：

public class Solution {
    public int findKthSmallest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        
        int len = nums.length;
        
        return quickSelect(nums, k, 0, len - 1);
    }
    
    private int quickSelect(int[] nums, int k, int start, int end) {
        
        //Choose a pivot randomly
        Random rand = new Random();
        int index = rand.nextInt(end - start + 1) + start;
        int pivot = nums[index];
        swap(nums, index, end);
        
        int left = start, right = end;
        
        while(left < right) {
            if (nums[left++] >= pivot) {
                swap(nums, --left, --right);
            }
        }
        //left is now pointing to the first number that is greater than or equal to the pivot
        swap(nums, left, end);
        
        //m is the number of numbers that is smaller than pivot
        int m = left - start;
        
        if (m == k - 1) { //in order to find the kth smallest number, there must be k - 1 number smaller than it 
            return pivot;
        }
        else if (k <= m) { //target is in the left subarray
            return quickSelect(nums, k, start, left - 1);
        }
        else { 
            //target is in the right subarray, but need to update k 
            //Since we have discarded m numbers smaller than it which is in the right subarray
            return quickSelect(nums, k - m, left, end);
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

注意：在上節(jié)和本節(jié)中給出的算法和代碼無法處理數(shù)組中有重復的情況。對于數(shù)組中有重復數(shù)字的情況，可以先掃描整個數(shù)組，利用HashSet或其他數(shù)據(jù)結構得到所有唯一的數(shù)字，然后使用本算法處理。

Quick Select 復雜度分析

1. 時間復雜度
   完整的平均時間復雜度分析非常復雜，在這里不再贅述。有興趣的可以看這里。
   一般來說，因為我們才用了隨機選取pivot的過程，平均來看，我們可以假設每次pivot都能選在中間位置。設算法時間復雜度為T(n)。在第一層循環(huán)中，我們將pivot與n個元素進行了比較，這個時間為cn 。
   所以第一步時間為：T(n) = cnc + T(n/2)。其中T(n/2)為接下來遞歸搜索其中一半的子數(shù)組所需要的時間。
   在遞歸過程中，我們可以得到如下公式：
   T(n/2) = c(n/2) + T(n/4)
T(n/4) = c(n/4) + T(n/8)
...
T(2) = 2*c + T(1)
T(1) = 1*c
   將以上公式循環(huán)相加消除T項可以得到：
   T(n) = c(n + n/2 + n/4 + n/8 + ... + 2 + 1) = 2n = O(n)
   因此得到Quick Select算法的時間復雜度為O(n)。

2. 空間復雜度
   算法沒有使用額外空間，swap操作是inplace操作，所以算法的空間復雜度為O(1)。