Leetcode: 215 disorderly to find the first big k element in the array

题目来源

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

题目描述

题目解析

快排

The original array is requiredkBig problems can be converted into firstsize - k + 1小的问题

思路

• Randomly select a number from an unordered arrayV,然后对VDo the Dutch flag problem for the entire array.此后,<V的在左边,=V的在中间,>V的在右边
• stop if hit,如果没有命中,Then go back to the first step according to the actual choice of left or right
• 时间复杂度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;
    }
};

优先级队列

思路

• The only one has a length of k的小根堆,Keep the element clock in the queue at k个
• 遍历数组nums,After enqueuing an element,Pops the smallest element at the top of the heap immediately
• 遍历完成之后,堆顶的元素就是第k大的数字

ps：求第kLarge numbers are piled with small roots,求第kSmall numbers are piled up with large roots

时间复杂度O(N*logK)

什么时候用？

在数据量很大的时候,可以实现「在线算法」,No need to read all the data into memory at once.

实现

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();
    }
};