数组中第K大(小)的元素

127 阅读 0 评论 84 点赞

我是靠谱客的博主淡定小蘑菇，这篇文章主要介绍数组中第K大(小)的元素，现在分享给大家，希望可以做个参考。

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

这是一道排序问题？显然当数组元素N很大时，采用一般O(N^2)的排序算法(如冒泡排序)一定会超时。

所以这里可以使用快排和堆排。这里快排和堆排的思想就不详细介绍了，有兴趣的可以去看我的其他文章或者直接baidu一下。

1.直接快速排序，对整个数组进行排序(156ms)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
lass Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        quick_sort(nums, 0, nums.size() - 1);
        return nums[nums.size() - k];
    }
    void quick_sort(vector<int>& nums, int l, int r){

        if(l < r){
            int pivot = partition(nums, l, r);
            quick_sort(nums, l, pivot - 1);
            quick_sort(nums, pivot + 1, r);
        }
    }

    int partition(vector<int>& nums, int l, int r){
        int p = nums[l];//i的位置已经记录下来
        int i = l, j = r;
        while(i < j){
            //先将大的往后移动
            while(i < j && nums[j] >= p){
                j --;
            }
            nums[i] = nums[j];//右边第一个比p小的数
            while(i < j && nums[i] <= p){
                i ++;
            }
            nums[j] = nums[i];//左边第一个比p大的数
        }
        nums[i] = p;
        return i;
    }
};

2.题目要求是找到第K个大的数即可，所以在quick_sort()函数中，每次partition返回的pivot的索引值和K进行比较，就可以每次减少一部分的排序：(52ms)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 int quick_sort(vector<int>& nums, int l, int r, int k){

        if(l == r) return nums[l];
        int pivot = partition(nums, l, r);
        if(pivot == nums.size() - k){
            return nums[pivot];
        }
        else if(pivot > nums.size() - k){//比目标值大，在左边
            return quick_sort(nums, l, pivot - 1, k);
        }
        else{ 
            return quick_sort(nums, pivot + 1, r, k);
        }
    }

3.在快排中，选择pivot对于整体速度影响很大，所以这里可以采用随机选择index的方法。在partition()中加入以下代码：(16ms)

复制代码

1
2
3
4
srand(time(NULL));//随机种子
int r_pos = rand() % (r - l + 1) + l;

swap(nums[l], nums[r_pos]);

4.堆排序

建(大顶)堆-调整-堆排序(“取出前k个大的数即可”)

复制代码

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        
        return buildHeap(nums, k);
    }

int buildHeap(vector<int>& nums, int k){
        //建成一个大顶堆
        int n = nums.size();
        for(int i = n / 2; i >= 0; -- i){
            downAdjust(nums, i, n);
        }
        
        for(int j = 0; j < k; j ++){
            swap(nums[0], nums[n - 1 - j]);
            downAdjust(nums, 0, n - 1 - j);
            //堆排序，将最大的，第二大的...，第k大的依次“取出”
        }
        return nums[n - k];
    }

void downAdjust(vector<int>& nums, int i, int n){
        //left & right child-node 2*i + 1 / 2*i + 2
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int maxidx = i;

if(l < n && nums[l] > nums[maxidx]){   
            maxidx = l;
        }
        if(r < n && nums[r] > nums[maxidx]){
            maxidx = r;
        }
        if(maxidx != i){
            swap(nums[i], nums[maxidx]);//maxidx位置和原i位置交换
            downAdjust(nums, maxidx, n);
        }
    }
 
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        
        return buildHeap(nums, k);
    }

    int buildHeap(vector<int>& nums, int k){
        //建成一个大顶堆
        int n = nums.size();
        for(int i = n / 2; i >= 0; -- i){
            downAdjust(nums, i, n);
        }
        
        for(int j = 0; j < k; j ++){
            swap(nums[0], nums[n - 1 - j]);
            downAdjust(nums, 0, n - 1 - j);
            //堆排序，将最大的，第二大的...，第k大的依次“取出”
        }
        return nums[n - k];
    }

    void downAdjust(vector<int>& nums, int i, int n){
        //left & right child-node 2*i + 1 / 2*i + 2
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int maxidx = i;

        if(l < n && nums[l] > nums[maxidx]){   
            maxidx = l;
        }
        if(r < n && nums[r] > nums[maxidx]){
            maxidx = r;
        }
        if(maxidx != i){
            swap(nums[i], nums[maxidx]);//maxidx位置和原i位置交换
            downAdjust(nums, maxidx, n);
        }
    }
 
};