在未排序的数组中找到第 k 个最大的元素
//快排 //注意找到轴值的索引等于k即可停止,大于k时排左边,否则排右边 class Solution { public: int QuickSort(vector<int>& nums, int left, int right, int k) { //if(left>=right)一定能找到,所以不需要考虑一边全遍历完的情况 int central = partition(nums, left, right); if (central == k) return nums[central]; if (central > k) return QuickSort(nums, left, central - 1, k);//什么时候找到什么时候return else return QuickSort(nums, central + 1, right, k); } int partition(vector<int>& nums, int left, int right) { srand(time(0)); int pivot = rand() % (right - left + 1) + left; swap(nums[left], nums[pivot]); int lt = left;//less than 小于等于lt的一定是小于privot元素的 for (int i = left + 1; i <= right; i++) { if (nums[i] < nums[left]) { lt++; swap(nums[lt], nums[i]); } } swap(nums[left], nums[lt]); return lt;//中心位置 } int findKthLargest(vector<int>& nums, int k) { return QuickSort(nums, 0, nums.size() - 1, nums.size() - k); } };
快排排序:
//需要两个函数 //void QuickSort(vector<int>& nums, int left, int right)用来递归,找到轴值,递归左右两边 //int partition(vector<int>& nums, int left, int right) 负责找到轴值,小于它的放左边,大于它的放右边,并返回中心轴值所在索引 class Solution { public: void QuickSort(vector<int>& nums, int left, int right) { if (left >= right)//当左边没有元素的时候,会出现left<right的情况;只有一个元素时相等 return; int central = partition(nums, left, right);//找到轴值,把低于它的放左边,高于他的放右边 QuickSort(nums, left, central - 1);//继续对左边排序 QuickSort(nums, central + 1, right);//继续对一边排序 } int partition(vector<int>& nums, int left, int right) { srand(time(0)); int pivot = rand() % (right - left + 1) + left;//找到随机轴值,交换至首位 swap(nums[left], nums[pivot]); int lt = left;//less than lt的本身和左边一定是小于privot元素的,从首位开始 for (int i = left + 1; i <= right; i++) {//i从首位右边开始遍历,大于轴值的不动,小于轴值的交换 if (nums[i] < nums[left]) { lt++; //lt右移,腾出位置将小于的值交换过来,保持lt左边和本身都是小于轴值的 swap(nums[lt], nums[i]); } } swap(nums[left], nums[lt]);//将首位的轴值交换到lt位置 此时:小于 轴值 大于 return lt;//轴值所在的中心位置 } void findKthLargest(vector<int>& nums) { QuickSort(nums, 0, nums.size() - 1); } };