LeetCode 数组中的第K个最大元素

超、凢脫俗 2023-06-04 14:56 6阅读 0赞

题目链接：[https://leetcode-cn.com/problems/kth-largest-element-in-an-array/][https_leetcode-cn.com_problems_kth-largest-element-in-an-array]

### 题目大意： ###

变换一下题意就是求第 k 小。

### 分析1： ###

利用库函数 nth\_element(a + l, a + k, a + r), 它会使 a 这个数组中区间 \[l, r) 内的第 k 小的元素处在第 k 个位置上(相对位置),但是它并不保证其他元素有序！

### 代码如下(期望O(N))： ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 class Solution {
    2 public:
    3     int findKthLargest(vector<int>& nums, int k) {
    4         k = nums.size() - k + 1;
    5         nth_element(nums.begin(), nums.begin() + k - 1, nums.end());
    6         return nums[k - 1];
    7     }
    8 };

### 分析2: ###

用一个大小为 k 的大顶堆维护前 k 个元素.

### 代码如下(O(Nlogk))： ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 class Solution {
     2 public:
     3     int findKthLargest(vector<int>& nums, int k) {
     4         k = nums.size() - k + 1;
     5         priority_queue< int > topK;
     6         
     7         for(int i = 0; i < k; ++i) topK.push(nums[i]);
     8         for(int i = k; i < nums.size(); ++i) {
     9             if(nums[i] < topK.top()) {
    10                 topK.pop();
    11                 topK.push(nums[i]);
    12             }
    13         }
    14         
    15         return topK.top();
    16     }
    17 };

### 分析3: ###

利用BFPRT算法.

### 代码如下(最坏O(N))： ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 class Solution {
     2 public:
     3     int findKthLargest(vector<int>& nums, int k) {
     4         return BFPRT(nums, nums.size() - k, 0, nums.size());
     5     }
     6     
     7     // 找[beg, end)的第k小,这里的k不是这个范围上的第k小,是整个数组的第k小
     8     int BFPRT(vector<int>& nums, int k, int beg, int end) {
     9         if(nums.size() == 1) return nums[k];
    10         vector<int> medians;
    11         int bestMid;
    12         int N = end - beg;
    13         
    14         // 每5个数一组求中位数
    15         for(int i = beg; i < end; i += 5) {
    16             if(i + 4 < end) medians.push_back(getMedian(nums, i, i + 5)); // 左闭右开
    17             else medians.push_back(getMedian(nums, i, end));
    18         }
    19         bestMid = getMedian(medians, 0, medians.size()); // 求中位数的中位数
    20         
    21         int lend, rbeg;
    22         partition(nums, beg, end, bestMid, lend, rbeg);
    23         
    24         if(k < lend) {
    25             return BFPRT(nums, k, beg, lend);
    26         }
    27         else if(k >= rbeg) {
    28             return BFPRT(nums, k, rbeg, end);
    29         }
    30         else {
    31             return bestMid;
    32         }
    33     }
    34     
    35     // 按照 mid 进行划分
    36     void partition(vector<int>& a, int beg, int end, int mid, int &lend, int &rbeg) {
    37         int l = beg - 1;
    38         int r = end;
    39         int p = beg;
    40         
    41         while(p < r) {
    42             if(p == l || a[p] == mid) ++p;
    43             else if(a[p] < mid) swap(a[p], a[++l]);
    44             else swap(a[p], a[--r]);
    45         }
    46         
    47         lend = l + 1;
    48         rbeg = r;
    49     }
    50     
    51     int getMedian(vector<int>& a, int beg, int end) {
    52         int mid = beg + ((end - beg) >> 1);
    53         if(end - beg > 5) return BFPRT(a, mid, beg, end);
    54         insertSort(a, beg, end); // 元素个数小于等于5个就用插入排序
    55         return a[mid];
    56     }
    57     
    58     void insertSort(vector<int>& a, int beg, int end) {
    59         for(int i = beg + 1; i < end; ++i) {
    60             for(int j = i; j > beg; --j) {
    61                 if(a[j] < a[j - 1]) swap(a[j], a[j - 1]);
    62                 else break;
    63             }
    64         }
    65     }
    66 };

转载于:https://www.cnblogs.com/zaq19970105/p/11466820.html

[https_leetcode-cn.com_problems_kth-largest-element-in-an-array]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/31de30696a15473bad1a667b4f0570d2.png