關于我的 Leetcode 題目解答换怖，代碼前往 Github：https://github.com/chenxiangcyr/leetcode-answers
快速選擇是一種從無序列表找到第k小元素的選擇算法甩恼。它從原理上來說與快速排序有關。同樣地沉颂，它在實際應用是一種高效的算法条摸，具有很好的平均時間復雜度，然而最壞時間復雜度則不理想铸屉。
快速選擇及其變種是實際應用中最常使用的高效選擇算法钉蒲。
快速選擇的總體思路與快速排序一致，選擇一個元素作為基準來對元素進行分區(qū)彻坛，將小于和大于基準的元素分在基準左邊和右邊的兩個區(qū)域顷啼。不同的是踏枣，快速選擇并不遞歸訪問雙邊，而是只遞歸進入一邊的元素中繼續(xù)尋找钙蒙。這降低了平均時間復雜度茵瀑，從O(n log n)至O(n)，不過最壞情況仍然是O(n2)躬厌。
示例：
從數組中找出第 k 小的元素：
// find the kth **smallest** element in an unsorted array
public int quickSelect(int[] nums, int k) {
int i = 0;
int j = nums.length - 1;
while(i <= j) {
int partitionIdx = partition(nums, i, j);
if((k - 1) == partitionIdx) {
return nums[partitionIdx];
}
else if((k - 1) < partitionIdx) {
j = partitionIdx - 1;
}
else {
i = partitionIdx + 1;
}
}
return 0;
}
// same as qucik sort
public int partition(int[] nums, int start, int end) {
if(start == end) {
return start;
}
int pivot = nums[start];
while(start < end) {
// find first smaller element from right
while(start < end && nums[end] >= pivot) {
end--;
}
nums[start] = nums[end];
// find first larger element from left
while(start < end && nums[start] <= pivot) {
start++;
}
nums[end] = nums[start];
}
nums[start] = pivot;
return start;
}
引用：
