本文主要是介绍LCR 076. 数组中的第 K 个最大元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
LCR 076. 数组中的第 K 个最大元素
题目链接:LCR 076. 数组中的第 K 个最大元素
下面这个题与这个题一样:
题目链接:215. 数组中的第K个最大元素
这个代码只能通过第一个题,如下:
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {quickSort(nums,0,nums.size()-1);return nums[nums.size()-k];}//快速排序void quickSort(vector<int>& nums,int low,int high){if(low>=high)return;int partitionpivot=partition(nums,low,high);quickSort(nums,low,partitionpivot-1);quickSort(nums,partitionpivot+1,high);}int partition(vector<int>&nums,int low,int high){int temp=nums[low]; while(low<high){while(low<high&&nums[high]>=temp)high--;swap(nums[low],nums[high]);while(low<high&&nums[low]<=temp)low++;swap(nums[low],nums[high]);}nums[low]=temp;return low;}
};
这个代码两个题都能通过,如下:
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {vector<int> temp;temp.push_back(0);for(int i=0;i<nums.size();i++){temp.push_back(nums[i]);}HeapSort(temp,nums.size());return temp[temp.size()-k];}//在含有n个元素的堆中添加一个元素,并调整为堆void HeadAdjust(vector<int>& arr, int i, int n)//调整为大根堆{arr[0] = arr[i];for (int j = 2 * i; j <= n; j *= 2){if (j < n && arr[j] < arr[j + 1])j++;if (arr[j] <= arr[0])break;else{arr[i] = arr[j];i = j;}}arr[i] = arr[0];}void HeapSort(vector<int>& arr, int n)//递增排序{for (int i = n / 2; i > 0; i--)HeadAdjust(arr, i, n);for (int i = n; i > 1; i--){swap(arr[1], arr[i]);HeadAdjust(arr, 1, i - 1);}}
};
这篇关于LCR 076. 数组中的第 K 个最大元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!