在數組中找到第k大的元素

您在真實的面試中是否遇到過這個題？? Yes 例子

給出數組[9,3,2,4,8]。第三大的元素是4

給出數組?[1,2,3,4,5]。第一大的元素是5，第二大的元素是4，第三大的元素是3，以此類推

注意

你能夠交換數組中的元素的位置

挑戰

要求時間復雜度為O(n），空間復雜度為O(1）

標簽?Expand??

相關題目?Expand?

分析：利用快排的思想。不斷partition,

代碼：

class Solution { public:/** param k : description of k* param nums : description of array and index 0 ~ n-1* return: description of return*/int kthLargestElement(int k, vector<int> nums) {// write your code herereturn findKthLargestElement(k,nums,0,nums.size()-1);}int findKthLargestElement(int k,vector<int>& nums,int start,int end){if(start==end)return nums[start];int index = partition(nums,start,end);if(end-index+1==k)return nums[index];else if(end-index+1>k)return findKthLargestElement(k,nums,index+1,end);elsereturn findKthLargestElement(k-(end-index+1),nums,start,index-1);}int partition(vector<int>&nums,int start,int end){int x = (start+end)/2;swap(nums[start],nums[x]);int i = start+1;int j = i;while(i<=end&&j<=end){if(nums[j]<nums[start]){swap(nums[i],nums[j]);i++;}j++;}swap(nums[start],nums[i-1]);return i-1;} };

轉載于:https://www.cnblogs.com/yangykaifa/p/7007226.html

總結

以上是生活随笔為你收集整理的LintCode-第k大元素的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。