數組中第K大元素

在面試的時候遇到過這個問題，后來在leetcode上也遇到了這個問題，于是記錄下來以便以后快速回憶。

題目有多種思路，全排序是比較直觀的想法，然而最低的時間復雜度為O(nlgn),并且不符合該題目的初衷。

題目更多想問的是如何在不進行全排序的條件下找到數組中第K大的元素，個人認為比較被面試官中意的解答有兩個(理應也有其他的..)，如下：

構建最大堆

簡單分析時間復雜度: 構建堆的時間O(n)，k次取最大元素要k(lgn),最終的時間復雜度為O(n+klgn).

顯然是比全排序要好一些，但是當時面試的時候我回答這個思路，面試官認為并不是一個好的思路，因為面試官認為構建最大堆更適合題目：求數組中前K大的元素(維護一個大小為K的最大堆).
然而我還是認為這是一個可以的思路…..恩，代碼還是貼一下，以后就省事了..

int heap_size;int parent(int idx) {return (idx - 1) >> 1; //求父節點}int left(int idx) {return (idx << 1) + 1;//左子樹}int right(int idx) {return (idx << 1) + 2;//右子樹}void max_heapify(vector<int>& nums, int idx) {int largest = idx;int l = left(idx), r = right(idx);if (l < heap_size && nums[l] > nums[largest]) largest = l;if (r < heap_size && nums[r] > nums[largest]) largest = r;if (largest != idx) {swap(nums[idx], nums[largest]);max_heapify(nums, largest);}}//構建最大堆，從非葉子節點開始操作,可證明時間復雜度是O(n)void build_max_heap(vector<int>& nums) {heap_size = nums.size();for (int i = (heap_size >> 1) - 1; i >= 0; i--)max_heapify(nums, i);}int findKthLargest(vector<int>& nums, int k) {build_max_heap(nums);for (int i = 0; i < k; i++) {swap(nums[0], nums[heap_size - 1]);heap_size--;max_heapify(nums, 0);}//不斷交換末尾元素和最大元素，之后重新max_heapifyreturn nums[heap_size];}

---

快速排序思路

該思想類似快速排序：

以某一個元素為pivot元素，將元素分為兩個集合，一個集合元素比pivot小，另一個比pivot大。

若比pivot大的元素數目正好為k-1，那么pivot就是我們要找到元素；若比pivot大的元素為m(小于k), 那么就在比pivot小的集合里面找第(k-m)大的元素; 若是比pivot大的元素為m(大于k)，那就繼續在該集合里面找第k大的元素。

重復上面步驟，直到找到第k大的元素

代碼如下：

int partition(vector<int>& nums, int i, int j){//類似快速排序的分組if (i == j) return i;int pivot = nums[i];std::swap(nums[i], nums[j]);int i0 = i;for(int k = i; k < j; k ++){if(nums[k] <= pivot){std::swap(nums[k], nums[i0 ++]);}}std::swap(nums[i0], nums[j]);return i0;}int findKthEle(vector<int>& nums, int i, int j,int k){int index = partition(nums,i,j);int length = j-index+1;if(length == k)return nums[index];else if(length > k)return findKthEle(nums,index+1,j,k);else if(length <k)return findKthEle(nums,i,index-1,k-length);}int findKthLargest(vector<int>& nums, int k) {size_t len = nums.size();return findKthEle(nums,0,len-1,k);}

時間復雜度：
該算法的平均時間復雜度為O(N)（詳細的推導過程看算法導論9.2節）,最壞情況為N^2，即每次劃分把數組變為為（n-1） 和1的兩斷。

同時算法導論上有關于O(n)的算法(9.3節)，其思路是選擇pivot元素時是通過選擇多組元素中的中位數，根據這個元素來劃分，能夠得到最壞情況為線性時間的選擇算法（具體推導我還真是吃不消）。

看了算法導論以及網上相關的博客，發現這是個經典的老題目了…然而我并沒有研究的非常透徹…

總結

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

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