leetcode

0 // sort: O(nlogn)

1 class Solution {

2 public:

3 vector<string> topKFrequent(const vector<string> &words, int k) {

4 unordered_map<string, int> um;

5 for (const auto &w : words)

6 um[w]++;

7

8 vector<pair<int, string>> vec(um.size());

9 vector<string> res(k);

10

11 int count = 0;

12 for (const auto &[k, v] : um)

13 vec[count++] = {-v, k};

14 sort(vec.begin(), vec.end());

15 for (int i = 0; i < k; i++)

16 res[i] = vec[i].second;

17

18 return res;

19 }

20 };

21

22 // heap: O(nlogk)

23 class Solution {

24 typedef pair<string, int> psi;

25 static constexpr const auto cmp = [](const psi &p1, const psi &p2) {

26 if (p1.second == p2.second) return p1.first < p2.first;

27 return p1.second > p2.second;

28 };

29

30 public:

31 vector<string> topKFrequent(const vector<string> &words, int k) {

32 unordered_map<string, int> um;

33 for (const auto &w : words)

34 um[w]++;

35

36 priority_queue<psi, vector<psi>, decltype(cmp)> pq(cmp);

37 vector<string> res(k);

38

39 for (auto it : um) {

40 pq.push(it);

41 if (pq.size() > k) pq.pop();

42 }

43

44 int count = k - 1;

45 while (!pq.empty())

46 res[count--] = pq.top().first, pq.pop();

47

48 return res;

49 }

50 };