数组中的第K个最大元素

提示注意一下本题题意与此处代码的避免差一错误的细节。class Solution { public: int findKthLargest(vectorint nums, int k) { quickSelect(nums, 0, nums.size() - 1, k - 1); return nums[k - 1]; } ​ void quickSelect(vectorint arr, const int first, const int last, int k) { if (first last) { return; } ​ // 优化随机取一个数 int randIdx first (rand() % (last - first 1)); swap(arr[randIdx], arr[first]); ​ int left first; int right last; int border arr[left]; while (left right) { while (left right border arr[right]) { right -1; } arr[left] arr[right]; while (left right border arr[left]) { left 1; } arr[right] arr[left]; } arr[left] border; ​ // 判断是否满足k个 const int borderIdx left; // 满足停止递归 if (borderIdx k) { return; } // 足够递归左侧 else if (borderIdx k) { quickSelect(arr, first, borderIdx - 1, k); } // 不够递归右侧 else { quickSelect(arr, borderIdx 1, last, k); } } };到此我们学习了基于分治思路的快速排序算法且用随机选点进行了优化并分析其原理衍生得到了快速选择的方法。就拿其他同为排序的算法来说如通过对插入排序的改良有了更强大的希尔排序又如基于堆排序的思路可以实现出自己的优先队列的数据结构。所以说只要我们仔细研究各种经典算法本质原理就能衍生更强大的功能