LeetCode 215 Kth Largest Element in an Array

    
        标签：
        
            设计数据结构
        
            LeetCode
        
    发布于：2022-02-11 14:48:41
    编辑于：2022-03-01 15:56:47
    浏览量：1034

概述

https://leetcode.com/problems/kth-largest-element-in-an-array/

排序法

显然可以直接排序然后直接取第 K 个。但我们实际上没必要对所有元素排序。

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

最大堆 / 优先级队列

https://labuladong.gitee.io/algo/2/20/53/

别问为啥要自己实现最大堆，问就是本意如此。

class Solution {
public:
    class MaxHeap {
    public:
        vector<int> arr = { INT_MAX };
        int size = 0;
        void push(int n) {
            if (size + 1 == arr.size()) {
                arr.push_back(n);
            } else {
                arr[size + 1] = n;
            }
            size ++;
            swim(size);
        }
        
        int pop() {
            int top = arr[1];
            swap(1, size);
            size --;            
            sink(1);
            return top;
        }
            
    private:
        void swim(int n) {
            while (p(n) > 0 && arr[n] > arr[p(n)]) {
                swap(n, p(n));
                n = p(n);
            }
        }
        
        void sink(int n) {
            while (true) {
                int ln = l(n);
                int rn = r(n);
                if (ln > size) return;
                int maxIdx = ln;
                if (rn <= size && arr[rn] > arr[ln]) maxIdx = rn;
                if (arr[n] >= arr[maxIdx]) return;
                swap(n, maxIdx);
                n = maxIdx;
            }
        }
        
        void swap(int i, int j) {
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
        
        int p(int n) {
            return n / 2;
        }
        
        int l(int n) {
            return 2 * n;
        }
        
        int r(int n) {
            return 2 * n + 1;
        }
    };
    
    int findKthLargest(vector<int>& nums, int k) {
        MaxHeap maxHeap;
        for (auto n : nums) {
            maxHeap.push(n);
        }
        int ans;
        for (int i = 1; i <= k; i ++) {
            ans = maxHeap.pop();
        }
        return ans;
    }
};

基于快排思想的快速选择算法

实现的时候注意：

rand() 还是有必要的，LeetCode 会故意用倒序的 case 恶心你。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return helper(nums, k - 1, 0, nums.size() - 1);
    }
    
    int helper(vector<int>& nums, int k, int l, int r) {
        int m = partition(nums, l, r);
        if (m == k) {
            return nums[m];
        } else if (m > k) {
            return helper(nums, k, l, m - 1);
        } else {
            return helper(nums, k, m + 1, r);
        }
    }
    
    int partition(vector<int>& nums, int l, int r) {
        if (l + 1 == r) {
            if (nums[l] < nums[r]) swap(nums[l], nums[r]);
            return l;
        }
        if (l == r) return l;
        int randIdx = rand() % (r - l) + l;
        swap(nums[randIdx], nums[r]);
        int t = nums[r];
        int j = l;
        for (int i = l; i <= r - 1; i ++) {
            if (nums[i] > t) {
                swap(nums[i], nums[j]);
                j ++;
            }
        }
        swap(nums[j], nums[r]);
        return j;
    }
};

上面这个 partition 实现的是不是很脏？

实际上上面那个 l + 1 == r 的 case 可以去掉。

那个 l == r 的 case 是为了避免 rand() 对 0 取余，所以不能去掉。

Links: leetcode-215-kth-largest-element-in-an-array