LeetCode 题解（2）：排序

learn from cyc2018 and LeetCode

利用随机化快速排序的 RANDOMIZED_PARTITION 求解 Kth Element 问题。参考材料：CLRS笔记：快速排序

225. Kth Largest Element in an Array (medium)

问题描述

找出数组中第 $k$ 大元素

1
2
3

// example
// Input: [3,2,3,1,2,4,5,5,6] and k = 4
// Output: 4

题解

参照 CLRS笔记：快速排序可以得到如下解：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return randomizedSelect(nums, 0, nums.size()-1, nums.size() - k + 1);
    }
private:
    int randomizedSelect(vector<int>& nums, int p, int r, int k){
        if(p == r)
            return nums[p];
        int q = randomizedPartition(nums, p, r);
        int i = q - p + 1;
        if(i == k)
            return nums[q];
        else if(k < i)
            return randomizedSelect(nums, p, q-1, k);
        else
            return randomizedSelect(nums, q+1, r, k-i);
    }
    int randomizedPartition(vector<int>& nums, int p, int r){
        int i = (rand() % (r-p+1))+ p;
        int tmp = nums[i];
        nums[i] = nums[r];
        nums[r] = tmp;
        return Partition(nums, p, r);
    }
    int Partition(vector<int>& nums, int p, int r){
        int x = nums[r];
        int i = p-1;
        int j = p;
        for(; j < r; ++ j)
            if(nums[j] < x){
                ++ i;
                int tmp = nums[j];
                nums[j] = nums[i];
                nums[i] = tmp;
            }
        int tmp = nums[j];
        nums[j] = nums[i+1];
        nums[i+1] = tmp;
        return i+1;
    }
};

347. Top K Frequent Elements (medium)

问题描述

寻找数组中出现频率第 $k$ 高的数字。

1
2
3

// example
// Input: nums = [1,1,1,2,2,3], k = 2
// Output: [1,2]

题解

比较简单的想法是，先用一个 map 存储每个数字以及其出现的频率，将其频率作为一个数组投入上题中获得第 $k$ 大元素。遍历整个 map 将值大于第 $k$ 大元素的键加入结果中。核心代码如下：

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> tmp;
        map<int, int>::iterator iter;
        for(int i = 0; i < nums.size(); ++ i){
            iter = tmp.find(nums[i]);
            if(iter == tmp.end())
                tmp[nums[i]] = 1;
            else
                ++ tmp[nums[i]];    
        }
        vector<int> tmpvec;
        for(iter = tmp.begin(); iter != tmp.end(); ++ iter){
            tmpvec.push_back(iter->second);
        }
        int i = randomizedSelect(tmpvec, 0, tmpvec.size()-1, tmpvec.size()-k+1);
        vector<int> result;
        for(iter = tmp.begin(); iter != tmp.end(); ++ iter){
            if(iter->second >= i)
                result.push_back(iter->first);
        }
        return result;
    }
}

但是结果出现问题：

时间复杂度与空间复杂度均较高。

参考 Solution 中利用堆来解决这一问题：

有时间可以试着实现一下 C++ 版本，看一下时间与空间结果。

LeetCode题解（2）：排序

LeetCode 题解（2）：排序

225. Kth Largest Element in an Array (medium)

问题描述

题解

相关问题

347. Top K Frequent Elements (medium)

问题描述

题解

相关问题