寻找第K大
题目描述
有一个整数数组,请你根据快速排序的思路,找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间),请返回第K大的数,保证答案存在。
思路解释
代码:
class Finder { public: int findKth(vector<int> a, int n, int K) { int res = 0, left = 0, right = n - 1; K = n - K; while(left <= right) { int i = QuickSort(a, left, right); if(i == K) return a[i]; else if(i < K) left = i + 1; else right = i - 1; } return 0; } int QuickSort(vector<int>& a, int low, int high) { if(low == high) return low; int i = low, j = high, key = a[low]; while(low < high) { while(low < high && a[high] >= key) high--; a[low] = a[high]; while(low < high && a[low] <= key) low++; a[high] = a[low]; } a[low] = key; return low; } };