C++题解 | #寻找第K大#

快速排序
利用快速排序（即每次都确定一个数据在从大到小的排序中所处的位置（下标））。
首先经过一遍排序，基本确定元素顺序，而后判断当前所指向数据的位置（假设为第M大，此时该位置的下标也为M）是否满足题意所求，及有M == K。若恰好为第K大，则直接返回该数据，否则，若M > K，则待求数据应当位于第M大之前；若M < K，则待求第K大位于第M大之后的数据中。（另外要注意是否要根据M的位置，更改K的值。特别是当M < K时，需要根据程序决定，是否将K变为K - M；其次，注意K值在函数传递时的情况，若数组下标从0开始，则应该改变K为K - 1）

class Solution { public: int QuickSort(vector<int> a, int l, int r, int K) { int left = l, right = r, s = a[l]; while (left < right) { while (left < right && a[right] < s) right--; if (left < right && a[right] > s) a[left] = a[right]; while (left < right && a[left] >= s) left++; if (left < right && a[left] < s) a[right] = a[left]; } int res = 0; a[left] = s; if (left == K) return a[left]; else if (left > K) { res = QuickSort(a, l, left - 1, K); } else { res = QuickSort(a, left + 1, r, K); } return res; } int findKth(vector<int> a, int n, int K) { int ans; ans = QuickSort(a, 0, n - 1, K - 1); return ans; } };