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

╰半橙微兮° 2023-02-28 01:40 33阅读 0赞

## 一、前言 ##

分类：Divide and Conquer。

问题来源LeetCode 215 难度：中等。

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

## 二、题目 ##

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

**示例1：**

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

**示例2：**

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

## 三、思路 ##

这里提供两种解决方法。

方法一：基于快速排序的选择方法。

**复杂度分析：**

*  时间复杂度：O(n)，最坏累加查找次数是n次。
 *  空间复杂度：O(log n)，递归使用栈空间的空间代价的期望为 O(logn)。

方法二：基于堆排序的选择方法。

**复杂度分析：**

*  时间复杂度：O(nlogn)，建堆的时间代价是 O(n)，删除的总代价是 O(klogn)，因为 k < nk<n，故渐进时间复杂为 O(n+klogn)=O(nlogn)。
 *  空间复杂度：O(logn)，即递归使用栈空间的空间代价。

## 四、编码实现 ##

//==========================================================================
    /*
    * @file    : 215_FindKthLargest.h
    * @label   : Divide and Conquer
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107440169
    * @author  : niebingyu
    * @date    : 2020/07/18
    * @title   : 215.数组中的第K个最大元素
    * @purpose : 在未排序的数组中找到第 k 个最大的元素。
    * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
    *
    * 示例1：
    * 输入: [3,2,1,5,6,4] 和 k = 2
    * 输出: 5
    * 
    * 示例2：
    * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
    * 输出: 4
    *
    * 来源：力扣（LeetCode）
    * 难度：中等
    * 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <string>
    #include <vector>
    #include <time.h>
    #include <algorithm>
    #include <assert.h>
    using namespace std;
    
    #define NAMESPACE_FINDKTHLARGEST namespace NAME_FINDKTHLARGEST {
    #define NAMESPACE_FINDKTHLARGESTEND }
    NAMESPACE_FINDKTHLARGEST
    
    // 方法一, 基于快速排序的选择方法
    class Solution_1 
    {
    public:
        int findKthLargest(vector<int>& nums, int k)
        {
            srand(time(0));
            return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
        }
    
    private:
        int quickSelect(vector<int>& a, int l, int r, int index) 
        {
            int q = randomPartition(a, l, r);
            if (q == index) 
                return a[q]; 
            else 
                return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
        }
    
        inline int randomPartition(vector<int>& a, int l, int r) 
        {
            int i = rand() % (r - l + 1) + l;
            swap(a[i], a[r]);
            return partition(a, l, r);
        }
    
        inline int partition(vector<int>& a, int l, int r) 
        {
            int x = a[r], i = l - 1;
            for (int j = l; j < r; ++j) 
            {
                if (a[j] <= x) 
                    swap(a[++i], a[j]);
            }
    
            swap(a[i + 1], a[r]);
            return i + 1;
        }
    };
    
    // 方法二，基于堆排序的选择方法
    class Solution_2
    {
    
    public:
        int findKthLargest(vector<int>& nums, int k)
        {
            int heapSize = nums.size();
            buildMaxHeap(nums, heapSize);
            for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i)
            {
                swap(nums[0], nums[i]);
                --heapSize;
                maxHeapify(nums, 0, heapSize);
            }
    
            return nums[0];
        }
    
    private:
        void maxHeapify(vector<int>& a, int i, int heapSize) 
        {
            int l = i * 2 + 1, r = i * 2 + 2, largest = i;
            if (l < heapSize && a[l] > a[largest]) 
                largest = l;
           
            if (r < heapSize && a[r] > a[largest]) 
                largest = r;
            
            if (largest != i) 
            {
                swap(a[i], a[largest]);
                maxHeapify(a, largest, heapSize);
            }
        }
    
        void buildMaxHeap(vector<int>& a, int heapSize) 
        {
            for (int i = heapSize / 2; i >= 0; --i) 
            {
                maxHeapify(a, i, heapSize);
            } 
        }
    };
    
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<int>& nums, int k, int expect)
    {
        Solution_1 s1;
        int result1 = s1.findKthLargest(nums, k);
    
        Solution_2 s2;
        int result2 = s2.findKthLargest(nums, k);
    
        if (result1 == expect && result2 == expect)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. " << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<int> nums = { 3,2,1,5,6,4 };
        int k = 2;
        int expect = 5;
    
        test("Test1()", nums, k, expect);
    }
    
    NAMESPACE_FINDKTHLARGESTEND
    // 测试 用例 END
    //
    void FindKthLargest_Test()
    {
        cout << "------ start 215.数组中的第K个最大元素 ------" << endl;
        NAME_FINDKTHLARGEST::Test1();
        cout << "------ end 215.数组中的第K个最大元素 --------" << endl;
    }

**执行结果：**

![20200719083613558.png][]

[https_leetcode-cn.com_problems_kth-largest-element-in-an-array]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
[20200719083613558.png]: /images/20230209/3a7a58b05cb34825b18b2d84613f959d.png