347. Top K Frequent Elements

发表于 | 分类于 | |

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

题意：找出出现次数最多的前k个数。

自己的想出来的解法不得不说有点像是诡计：维护一个map[数字] = 出现次数的结构，然后按照value值排序，挑选出前k个的key值。

但是这样的想法遇到一个问题，就是如何对map进行排序。

Google后发现因为map是以红黑树结构来存储数据，以维护其key有序。所以我们需要把map转化为序列存储的vector\后，再调用STL的sort方法对其进行排序。

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
//
// Created by chaopengz on 2017/11/6.
//

#include "head.h"

class Solution {
public:
    vector<int> topKFrequent(vector<int> &nums, int k)
    {
        int len = nums.size();
        map<int, int> m;
        for (int i = 0; i < len; ++i)
        {
            m[nums[i]] = 0;
        }
        for (int i = 0; i < len; ++i)
        {
            m[nums[i]]++;
        }

        vector<pair<int, int>> mapVector(m.begin(), m.end());

        sort(mapVector.begin(), mapVector.end(), cmp);

        vector<int> ans;
        for (int j = 0; j < k; ++j)
        {
            ans.push_back(mapVector[j].first);
        }

        return ans;

    }

    static bool cmp(pair<int, int> a, pair<int, int> b)
    {
        return a.second > b.second;
    }


};