【每日算法Day 82】面试经典题：求第K大数，我写了11种实现，不来看看吗？

godweiyang

发布于 2020-04-02 11:37:47

5670

发布于 2020-04-02 11:37:47

文章被收录于专栏：算法码上来算法码上来

题目链接

LeetCode 215. 数组中的第K个最大元素[1]

题目描述

在未排序的数组中找到第 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

解释：

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

题解

排序

对数组从大到小排序，取第个元素。

或者从小到大排序，取第个元素。

小根堆+库函数

c++ 自带 priority_queue<int> ，可以实现小根堆。

python 自带 heapq ，可以实现小根堆，同时还自带 nlargest 函数可以直接求出前大元素。

然后维护一个大小为的小根堆，保存最大的个数，堆顶就是第大的数。新元素入堆，如果堆中元素个数大于，就将堆顶元素出堆。

大根堆+库函数

c++ 自带 priority_queue<int, vector<int>, greater<int>> ，可以实现大根堆。

python 没有大根堆实现。

然后维护一个大小为的大根堆，保存最小的个数，堆顶就是第小的数，即第大的数。新元素入堆，如果堆中元素个数大于，就将堆顶元素出堆。

小根堆+手写

利用原地算法，直接将原数组当作一个小根堆。

首先对前个元素建立初始堆。然后遍历后面的元素，如果大于堆顶元素的话，就和堆顶元素交换位置，并调整堆。

小根堆大小始终为。

大根堆+手写

利用原地算法，直接将原数组当作一个大根堆。

首先对前个元素建立初始堆。然后遍历后面的元素，如果小于堆顶元素的话，就和堆顶元素交换位置，并调整堆。

大根堆大小始终为。

快速选择

思想类似于快速排序，首先随机选取一个元素，然后将区间内元素比小的都放在左边，比大的都放在右边。

然后看的下标，如果，那就说明就是第小（第大）的元素，直接返回即可。否则如果，那就说明第大元素在的右边区间内，递归寻找即可。否则就在左边区间，递归寻找。

代码

排序（c++）

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), greater<int>());
        return nums[k-1];
    }
};

小根堆+STL优先队列（c++）

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> Q;
        for (auto x : nums) {
            Q.push(x);
            while (Q.size() > k) Q.pop();
        }
        return Q.top();
    }
};

大根堆+STL优先队列（c++）

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> Q;
        for (auto x : nums) {
            Q.push(x);
            while (Q.size() > nums.size()-k+1) Q.pop();
        }
        return Q.top();
    }
};

小根堆+手写（c++）

class Solution {
public:
    void adjust(vector<int>& nums, int p, int s) {
        while (2*p+1 < s) {
            int c1 = 2*p+1;
            int c2 = 2*p+2;
            int c = (c2<s && nums[c2]<nums[c1]) ? c2 : c1;
            if (nums[c] < nums[p]) swap(nums[c], nums[p]);
            else break;
            p = c;
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        for (int i = k/2-1; i >= 0; --i) {
            adjust(nums, i, k);
        }
        for (int i = k; i < n; ++i) {
            if (nums[0] >= nums[i]) continue;
            swap(nums[0], nums[i]);
            adjust(nums, 0, k);
        }
        return nums[0];
    }
};

大根堆+手写（c++）

class Solution {
public:
    void adjust(vector<int>& nums, int p, int s) {
        while (2*p+1 < s) {
            int c1 = 2*p+1;
            int c2 = 2*p+2;
            int c = (c2<s && nums[c2]>nums[c1]) ? c2 : c1;
            if (nums[c] > nums[p]) swap(nums[c], nums[p]);
            else break;
            p = c;
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        for (int i = (n-k+1)/2-1; i >= 0; --i) {
            adjust(nums, i, (n-k+1));
        }
        for (int i = (n-k+1); i < n; ++i) {
            if (nums[0] <= nums[i]) continue;
            swap(nums[0], nums[i]);
            adjust(nums, 0, (n-k+1));
        }
        return nums[0];
    }
};

快速选择（c++）

class Solution {
public:
    int partition(vector<int>& nums, int l, int r) {
        int p = l+rand()%(r-l+1), m = l;
        swap(nums[p], nums[r]);
        for (int i = l; i < r; ++i) {
            if (nums[i] < nums[r]) {
                swap(nums[i], nums[m++]);
            }
        }
        swap(nums[m], nums[r]);
        return m;
    }

    int quickSelect(vector<int>& nums, int l, int r, int k) {
        if (l == r) return nums[l];
        int m = partition(nums, l, r);
        if (k == m+1) return nums[m];
        if (k < m+1) return quickSelect(nums, l, m-1, k);
        return quickSelect(nums, m+1, r, k);
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        srand((int)time(0));
        return quickSelect(nums, 0, n-1, n-k+1);
    }
};

排序（python）

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort(reverse=True)
        return nums[k-1]

小根堆+heapq（python）

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)[-1]

小根堆+手写（python）

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def adjust(nums, p, s):
            while 2*p+1 < s:
                c1, c2 = 2*p+1, 2*p+2
                c = c2 if (c2<s and nums[c2]<nums[c1]) else c1
                if nums[c] < nums[p]:
                    nums[c], nums[p] = nums[p], nums[c]
                else:
                    break
                p = c

        n = len(nums)
        for i in range(k//2-1, -1, -1):
            adjust(nums, i, k)
        for i in range(k, n):
            if nums[0] >= nums[i]: continue
            nums[0], nums[i] = nums[i], nums[0]
            adjust(nums, 0, k)
        return nums[0]

大根堆+手写（python）

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def adjust(nums, p, s):
            while 2*p+1 < s:
                c1, c2 = 2*p+1, 2*p+2
                c = c2 if (c2<s and nums[c2]>nums[c1]) else c1
                if nums[c] > nums[p]:
                    nums[c], nums[p] = nums[p], nums[c]
                else:
                    break
                p = c

        n = len(nums)
        for i in range((n-k+1)//2-1, -1, -1):
            adjust(nums, i, (n-k+1))
        for i in range((n-k+1), n):
            if nums[0] <= nums[i]: continue
            nums[0], nums[i] = nums[i], nums[0]
            adjust(nums, 0, (n-k+1))
        return nums[0]

快速选择（python）

import random

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def partition(nums, l, r):
            p, m = l+random.randint(0, r-l), l
            nums[p], nums[r] = nums[r], nums[p]
            for i in range(l, r):
                if nums[i] < nums[r]:
                    nums[m], nums[i] = nums[i], nums[m]
                    m += 1
            nums[m], nums[r] = nums[r], nums[m]
            return m
        
        def quickSelect(nums, l, r, k):
            if l == r: return nums[l]
            m = partition(nums, l, r)
            if k == m+1: return nums[m]
            if k < m+1: return quickSelect(nums, l, m-1, k)
            return quickSelect(nums, m+1, r, k)

        n = len(nums)
        return quickSelect(nums, 0, n-1, n-k+1)

参考资料

[1]

LeetCode 面试题 17.09. 第 k 个数: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-03-27，如有侵权请联系 cloudcommunity@tencent.com 删除

python

c++

编程算法

本文分享自算法码上来微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

python

c++

编程算法

登录后参与评论

0 条评论

热度