leetcode：215无序数组中找第k大的元素

题目来源

• leetcode：215无序数组中找第k大的元素

题目描述

题目解析

快排

原数组是要求第k大的问题可以转换为求第size - k + 1小的问题

思路

• 无序数组中随机选择一个数V，然后对V对整个数组做荷兰国旗问题。此后，<V的在左边，=V的在中间，>V的在右边
• 如果命中就停，如果没有命中，然后根据实际选择左侧或者右侧回到第一步
• 时间复杂度O(N)

动画

实现

class Solution {
    
    std::vector<int> partition(std::vector<int>& arr, int L, int R, int prio){
    
        int less = L - 1, more = R + 1, curr = L;
        while (curr < more){
    
            if(arr[curr] < prio){
    
                std::swap(arr[++less], arr[curr++]);
            }else if(arr[curr] > prio){
    
                std::swap(arr[curr], arr[--more]);
            }else{
    
                curr++;
            }
        }
        return {
    less + 1, more - 1};
    }

    // arr[L..R] 范围上，如果排序的话(不是真的去排序)，找位于index的数
    int process(std::vector<int> arr, int L, int R, int index){
    
        if(L == R){
      //
            return arr[L];
        }

        int pivot = arr[rand() % (R - L + 1) + L];
        auto range = partition(arr, L, R, pivot);
        if (index >= range[0] && index <= range[1]) {
    
            return arr[index];
        } else if (index < range[0]) {
    
            return process(arr, L, range[0] - 1, index);
        } else {
    
            return process(arr, range[1] + 1, R, index);
        }
    }
public:
    int findKthLargest(vector<int> &nums, int k){
    
        srand(time(0));
        int result = 0;
        int numsSize = int(nums.size());
        if (numsSize == 0 || k > numsSize)
        {
    
            return 0;
        }
        //寻找第kMIN小的数
        int kMin = numsSize - k + 1; //第k小
        result = process(nums, 0, numsSize - 1, kMin - 1);
        return result;
    }
};

优先级队列

思路

• 唯一一个长度为k的小根堆，保持队列中的元素时钟为k个
• 遍历数组nums，入队一个元素之后，立即弹出堆顶最小的元素
• 遍历完成之后，堆顶的元素就是第k大的数字

ps：求第k大的数用小根堆，求第k小的数用大根堆

时间复杂度O(N*logK)

什么时候用？

在数据量很大的时候，可以实现「在线算法」，不用一下子把所有数据读入内存。

实现

class Solution {
    
public:
    int findKthLargest(vector<int> &arr, int k){
    
        std::priority_queue<int , std::vector<int>, std::greater<>> minheap;
        for (int i = 0; i < k; ++i) {
    
            minheap.push(arr[i]);
        }

        for (int i = k; i < arr.size(); ++i) {
    
            if(arr[i] < minheap.top()){
    
                minheap.pop();
                minheap.push(arr[i]);
            }
        }

        return minheap.top();
    }
};