Cinte's Leetcode Record
0%

347. Top K Frequent Elements

Posted on Edited on In Disqus:
Symbols count in article: 2.3k Reading time ≈ 2 mins.

347. Top K Frequent Elements

Quick Select

快速排序，每次只排一半

T(n) : (1) Explore - LeetCode

b = 2, d=1,a=1

T(n) = T(n/2) + f(n)=T(n/2)+T(n)

1626147961860.png

那么T(n) 为 O(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
42
43
44
45
46
47
48
49
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        for(auto& num : nums)
            map[num] += 1;
        for(auto& it : map)
            unique.push_back(it.first);
        sort(0, unique.size() - 1, unique.size() - k);
        vector<int> ret;
        // for(int i = unique.size() - 1; i >= unique.size() - k; --i) // 注意这种情况是错误的，当unique.siez() - k为0时，因为unique.size()是无符号数，而i是有符号数，i与unique.size() - k比较时将会自动转换为无符号数比较，这时的i是一个极大的无符号数，将导致i为负数时仍旧成立，解决方法可以先将unique.size()转为int
        //     ret.push_back(unique[i]);
        for(auto i = unique.end() - 1; i != unique.end() - 1 - k; --i)
            ret.push_back(*i);
        return ret;
    }
private:
    vector<int> unique;
    unordered_map<int, int> map;
private:
    int patition(int lo, int hi, int pivot)
    {
        swap(unique[pivot], unique[lo]);
        int i = lo, j = hi + 1;
        int c = map[unique[lo]];
        while(i < j)
        {
            while(i < hi && map[unique[++i]] < c) {}
            while(j > lo && map[unique[--j]] > c) {}
            if(i >= j)
                break;
            swap(unique[i], unique[j]);
        }
        swap(unique[j], unique[lo]);
        return j;
    }
    void sort(int lo, int hi, const int& k)
    {
        if(lo >= hi)
            return;
        auto pivot = lo + (rand() % (hi - lo + 1));
        auto j = patition(lo, hi, pivot);
        if(j == k)
            return;
        else if(j > k)
            sort(lo, j - 1, k);
        else
            sort(j + 1, hi, k);
    }
};

review

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
42
43
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        for(auto num : nums)
            ++map[num];
        vector<int> r;
        for(auto [num, _] : map)
            r.push_back(num);
        sort(r, 0, r.size() - 1, k);
        return vector<int>(r.begin(), r.begin() + k);
    }
private:
    unordered_map<int, int> map;
    int partition(vector<int>& nums, int lo, int hi)
    {
        auto pivot = lo + (rand() % (hi - lo + 1));
        int i = lo, j = hi + 1;
        int c = map[nums[pivot]];
        swap(nums[pivot], nums[lo]);
        while(i < j)
        {
            while(i < hi && map[nums[++i]] > c) {}
            while(j > lo && map[nums[--j]] < c) {}
            if(i >= j)
                break;
            swap(nums[i], nums[j]);
        }
        swap(nums[lo], nums[j]);
        return j;
    }
    void sort(vector<int>& nums, int lo, int hi, int k)
    {
        if(lo >= hi)
            return;
        auto j = partition(nums, lo, hi);
        if(j == k - 1)
            return;
        if(j < k - 1)
            sort(nums, j + 1, hi, k);
        else
            sort(nums, lo, j - 1, k);
    }
};