在未排序的數(shù)組中找到第?k?個(gè)最大的元素。請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素。

示例 1:

輸入: [3,2,1,5,6,4] 和 k = 2 輸出: 5

示例?2:

輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4 輸出: 4

說明:

你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長度。

分析：這種問題老師講了很多解法，一步比一步的效率要好，這里我用了基于劃分的方法，類似于快排。

class Solution { public://根據(jù)第一個(gè)元素劃分位置int partition(vector<int>&nums,int low,int high){int temp=nums[low];int p=nums[low];while(low<high){while(low<high&&nums[high]<=temp)high--;nums[low]=nums[high];while(low<high&&nums[low]>=temp)low++;nums[high]=nums[low];}nums[low]=temp;return low;}int findKthLargest(vector<int>& nums, int k) {int begin=0,end=nums.size()-1;//如果把數(shù)據(jù)從大到小排序的話，第k大元素就是第k-1位置的元素。//當(dāng)k-1<position的話，就去劃分位置的左邊去找；如果k-1>position的話去劃分位置的右邊去找；相等的話直接返回。while(1){int position=partition(nums,begin,end);if(k-1==position)return nums[position];else if(k-1<position) end=position-1;else begin=position+1;}} };

?

轉(zhuǎn)載于:https://www.cnblogs.com/zfc888/p/10172336.html

總結(jié)

以上是生活随笔為你收集整理的DC-leetcode215数组中的第k大元素的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。