基本思想：
利用快速排序，只要找到第k个数，其左边的值都小于该元素，右边的值都大于该元素即可（左半区和右半区可以无序）。
代码如下：
代码中的k的值（k对数组中对应元素的索引）是转化后的值 如果是求第K小数，那么k = K - 1;如果是求第K大数，那么k = n - K; int partition(vector<int>& nums, int left, int right) { int pivotValue = nums[left]; while(left < right) { while(left < right && nums[right] >= pivotValue) right--; nums[left] = nums[right]; while(left < right && nums[left] <= pivotValue) left++; nums[right] = nums[left]; } nums[left] = pivotValue; return left; } int findKth(vector<int>& nums, int left, int right, int k) { if(left <= right) { int pivotInd = partition(nums, left, right); if(pivotInd == k) return nums[k]; else if(pivotInd < k) return findKth(nums, pivotInd + 1, right, k); else return findKth(nums, left, pivotInd - 1, k); } return -1; }