LeetCode 215. 数组中的第K个最大元素    原题链接    中等

作者： 作者的头像   有心人 ,  2021-08-22 11:00:57 ,  所有人可见 ,  阅读 1770

27


17

[toc]

题目

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

image-20210822101820362

面试考点

1. 考点1：能否实现解法的优化

  1. 暴力法：时间 O(nlogn)，空间 O(1)。
  2. 堆：最小堆：时间 O(nlogk), 空间 O(k) ；最大堆：时间 O(nlogn), 空间 O(logn)
  3. 快速选择：时间 O(n)，空间 O(logn) 的栈空间 可以 省去 从而优化到 O(1)

2. 考点2：是否了解 快速选择 算法

  • y总的快速排序 和 快速选择 模板 没有 用算法导论中 Partition，y总模板小而美。推荐 y 总代码。

3. 考点3：能否说明 堆算法 和 快速选择算法的适用场景。

  • 快速选择 只 适用于 确定数量的情况下，即静态不变的 情况。

  • 如果是动态情况，而不是确定数组量，则只能用堆的方法（最小堆 时间复杂度较优，最大堆的话需要插入新元素到堆（上浮），然后再堆调整 ）。

  • 面试时 看能不能 用 stl 的 堆，即 优先队列 priority_queue，不能的话 只能 手动建堆 并 调整堆了。

题解

1. 暴力解法

  • 时间复杂度：O(nlogn)。采用sort() 排序 O(nlogn)，返回 k - 1 下标 O(1)。
  • 空间复杂度：O(1)。

2. 堆： 最小堆 或者 最大堆

2.1 最小堆：时间 O(nlogk), 空间 O(k) .（最小堆 只需要维护 k 个结点）

  • 利用 stl 最小堆，没有 手动 实现 堆。

image-20210822100952453

// 最小堆: 时间 O(nlogk), 空间 O(k)
// 没有手动实现堆, 利用 STL 最小堆
#include <vector>
#include <queue>

class Solution {
public:
     int findKthLargest(vector<int>& nums, int k) {
         std::priority_queue<int, std::vector<int>, std::greater<int>> Q;  // 最小堆
         for(int i = 0; i < nums.size(); i++){
             if(Q.size()<k){
                 Q.push(nums[i]);
             }
             else if (Q.top() < nums[i]){
                 Q.pop();
                 Q.push(nums[i]);
             }
         }
         return Q.top();
     }
};

2.2 最大堆：时间 O(nlogn), 空间 O(logn).（最大堆 需要维护 n 个结点）

  • 力扣官方题解，利用最大堆，没用STL最大堆，自己手动实现最大堆。最大堆(时间 O(nlogn), 空间 O(logn))

image-20210529202813731

class Solution {
public:
     void maxHeapify(vector<int>& a, int i, int heapSize) {   // 此函数的功能是将索引i处a[i]结点进行下沉
         int left = i * 2 + 1, right = i * 2 + 2, largest = i;
         if (left < heapSize && a[left] > a[largest]) { // left < heapSize,还是<= ？，此处肯定是<，之所以没有等于是因为，最后一个元素的下标是heapSize-1,所以不可能与heapSize相等
             largest = left;
         }
         if (right < heapSize && a[right] > a[largest]) { // 此时的largest已经是和left比较过的了
             largest = right;
         }
         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) { // i = heapSize / 2最后一个非叶子结点

             maxHeapify(a, i, heapSize);
         }
     }

     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) {   //num.size()-k+1 ---> num.size()-(k-1), 返回第1大，不用循环；返回第2大，循环1次；返回第k大，循环k-1次。
             swap(nums[0], nums[i]); // 此处也可 swap(nums[0], nums[heapSize-1]);
             --heapSize;
             maxHeapify(nums, 0, heapSize);
         }
         return nums[0];
     }
};

最大堆方法思路：

  • 数组nums中存放的是二叉堆，因为二叉堆是完全二叉树，所以数组没有空间浪费，数组从nums[0] 到最后一个元素 nums[nums.size()-1]分别对应二叉堆按照层序遍历的顺序对应的元素。
  • 完全二叉树 用 层序遍历顺序 的 存储在数组 中的性质：父节点i（下标从0开始）的左子节点为2i+1，右子结点为2i+2。

  • void maxHeapify(vector[HTML_REMOVED]& a, int i, int heapSize) 函数的功能是将 二叉堆 数组a 索引 i 处 a[i] 结点进行下沉

  • 首先创建最大堆，从最后一个非叶子结点 i= heapSize / 2 开始，终止条件i>=0，然后i–遍历，将nums[i]进行下沉maxHeapify(a, i, heapSize)，从下往上进行堆下沉；

  • 进行堆删除，删除堆顶（最大元素位于堆顶nums[0]），堆调整，删除的时候从最后一个堆元素 a[i=heapSize-1] （heapSize=nums.size()）与堆顶nums[0] 交换，同时 heapSize– ,然后进行堆首结点nums[0]下沉，maxHeapify(nums, 0, heapSize)；之后遍历i–，依次将堆顶元素nums[0] 与 最后一个元素a[i=heapSize-1] 交换，heapSize– ，下沉....循环。终止条件是i>=0.
  • 初始值从nums.size()-1开始，循环1次返回的是第2大的，循环k-1次，即 nums.size()-(k-1)= nums.size-k+1 是返回第k大的。即终止条件是i>=nums.size-k+1

注意：

left < heapSize,还是 <= ？，此处肯定是<，之所以没有=是因为，二叉堆数组 最后一个元素的下标是heapSize-1，heapSize-1 < heapSize ，所以不可能与heapSize相等

3. 快速选择

3.1 力扣官方题解代码: (代码 较长)

  • 第K大，就是，数组下标为 (size- K) 。

image-20210822103903150

// 力扣官方题解 快选 代码，时间O(n), 空间(logn)
class Solution {
public:
    int quickSelect(vector<int>& a, int left, int right, int index) {
        int q = randomPartition(a, left, right);
        if (q == index) {
            return a[q];
        } else {
            return q < index ? quickSelect(a, q + 1, right, index) : quickSelect(a, left, q - 1, index);
        }
    }


    inline int randomPartition(vector<int>& a, int left, int right) {    // inline的作用
        int pivot_index = rand() % (right - left + 1) + left;    // 随机选择 pivot
        int pivot = a[pivot_index];
        swap(a[pivot_index], a[right]);     // 将轴值与数组最右边的值交换, a[right]中存放pivot

        int store_index = left;   // store_index指轴索引
        for (int i = left; i < right; i++) {
            if (a[i] <= pivot) {         // 其实此处pivot可以用a[right]替换，只不过代码可读性降低
                swap(a[store_index++], a[i]);  // 交换是为了将小于轴值的数，放在轴的左边
            }
        }     // 此时store_index 索引处的值 a[store_index]比pivot大
        swap(a[store_index], a[right]);   // 将轴存放到预期位置；轴左边的数均小于轴值，轴右边的值均大于轴值
        return store_index;
    }


    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0));
        return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);   // 第K大的值，数组下标为 (size- K)
    }
};

image-20210529203534670

快速选择方法主要思路：

  1. 随机选择一个pivot，swap( a[pivot_index], a[right] )，交换
  2. 遍历a[i]，设置store_index指示轴，当a[i]<pivot时，store_index++，同时将小于pivot的a[i] 与a[store_index]交换位置，交换是为了让小于pivot的a[i]位于轴的左侧
  3. 最后将 轴store_index处的值 与 a[right]互换，使a[store_index]处存的值时pivot，同时store_index就是pivot的索引，返回

需要注意的是：store_index++

3.2 y总代码（极其简洁，推荐）

3.2.1 y总代码 有递归栈空间. 时间O(n)，空间O(logn)

// 时间复杂度：O(n), 空间复杂度: 递归栈空间O(logn)
// y总 代码 没有 随机选取 x , 导致 用时比较长 44ms. 随机后 4ms
// 如果 x 每次都选 nums[l] 或 nums[r], 碰到 升序或降序的 极端样例, 时间O(n^2),, 用时会很久
// 而且 nums[l] 和 nums[r] 的代码边界不一样, 容易出错, 建议选 nums[l + r >> 1]
// 选取 nums[l] 的 用时 在 40ms 左右, 选取 nums[r]需要修改一下边界情况, 没有改, 应该也40ms左右
// 选取 nums[l + r >> 1] 跟 随机选取 nums[rand() % (r - l + 1) + l] 时间差不多, 在 4ms 左右
class Solution {
public:

    int quick_select(vector<int>& nums, int l, int r, int k) {
        if (l >= r) return nums[l];
        // int i = l - 1, j = r + 1, x = nums[l + r >> 1]; // 选取 nums[l], 极端样例 时间会很久
        int x = nums[rand() % (r - l + 1) + l], i = l - 1, j = r + 1; // 随机选取
        while (i < j) {
            do i ++ ; while (nums[i] > x);
            do j -- ; while (nums[j] < x);
            if (i < j) swap(nums[i], nums[j]);
        }
        if (k <= j - l + 1) return quick_select(nums, l, j, k);
        else return quick_select(nums, j + 1, r, k - (j - l + 1));
    }

    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0)); // 随机种子
        return quick_select(nums, 0, nums.size() - 1, k);
    }
};

3.2.2 y总快选 优化空间，去掉递归栈空间，直接用while循环. 时间O(n)， 空间O(1)

// 时间复杂度：O(n), 空间复杂度: O(1)
// y总 代码 去掉递归栈空间, 用 while 循环, 就不用 递归栈空间 了.
// 原来的 递归 只是 相同的代码, 只不过 递归时 递归的参数 区间端点值 l,r 以及 k变了
// 这里 while 每次循环 也是 用 相同的代码, 只不过 是 每次循环之后 将 l,r 以及 k 更新
class Solution {
public:
     int quick_select(vector<int>& nums, int l, int r, int k) {
         while(true) {
             if (l == r) return nums[l];
             int i = l - 1, j = r + 1, x = nums[l + r >> 1]; // 选取 nums[l], 极端样例 时间会很久
             // int x = nums[rand() % (r - l + 1) + l], i = l - 1, j = r + 1; // 随机选取
             while (i < j) {
                 do i ++ ; while (nums[i] > x);
                 do j -- ; while (nums[j] < x);
                 if (i < j) swap(nums[i], nums[j]);
             }

             // 将 递归 的 参数l,r,k变化 改为 while 循环中 l,r,k 更新, 省去递归栈空间
             // if (k <= j - l + 1) return quick_select(nums, l, j, k);
             if (k <= j - l + 1) r = j;
             // else return quick_select(nums, j + 1, r, k - (j - l + 1));
             else k = k - (j - l + 1), l = j + 1; // 注意 k更新用到 l, 所以 l 更新应该在 k更新之后
         }
     }

     int findKthLargest(vector<int>& nums, int k) {
         srand(time(0)); // 随机种子
         return quick_select(nums, 0, nums.size() - 1, k);
     }
};

3 评论

用户头像
qbz666   2022-10-11 10:17         踩      回复

写的太好了呜呜呜呜

用户头像
猪啊猪   2021-10-03 18:33         踩      回复

捕捉一只校友 这位校友你好呀hh

用户头像
有心人   2021-10-03 19:55         踩      回复

nice~ 你好~