Just like quick sort, we use a partition function to split array into two parts, the left part of elements are all less than pivot, the right part of elements are all greater than pivot.

And reduce the search range in every iteration.

Overall time complexity O(N).

classSolution {

private: voidswap(vector<int>& a, int x, int y){ int t = a[y]; a[y] = a[x]; a[x] = t; }

intrandom(int a, int b){ return (int) (rand() % (b - a + 1)) + a; }

intpartition(vector<int>& nums, int left, int right, int index){ int pivot = nums[index]; swap(nums, index, right); int i = left - 1; for (int j=left; j<=right-1; j++) if (nums[j] <= pivot) swap(nums, ++i, j); swap(nums, right, i+1); return i+1; }

intquick_select(vector<int>& nums, int left, int right, int k){ while (left <= right) { int pivot = partition(nums, left, right, random(left, right)); if (pivot == k) return nums[k]; elseif (k > pivot) left = pivot + 1; else right = pivot - 1; } return-1; }