leetcode 347. Top K Frequent Elements 使用HashMap计数

Dear 丶 2022-06-07 01:16 245阅读 0赞

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.

这道题很简单,直接使用HashMap计数,然后排序即可。

代码如下:

  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.Comparator;
  4. import java.util.HashMap;
  5. import java.util.List;
  6. import java.util.Map;
  7. import java.util.Map.Entry;
  8. class Solution
  9. {
  10. public List<Integer> topKFrequent(int[] nums, int k)
  11. {
  12. List<Integer> res=new ArrayList<Integer>();
  13. if(nums==null || nums.length<=0 || k<=0 || k>=nums.length+1)
  14. return res;
  15. Map<Integer, Integer> map=new HashMap<Integer, Integer>();
  16. for(int i=0;i<nums.length;i++)
  17. map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
  18. List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
  19. Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
  20. @Override
  21. public int compare(Entry<Integer, Integer> a,Entry<Integer, Integer> b) {
  22. return b.getValue()-a.getValue();
  23. } });
  24. for(int i=0;i<k;i++)
  25. res.add(list.get(i).getKey());
  26. return res;
  27. }
  28. }

下面是C++的做法,直接统计计数即可

代码如下:

  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <unordered_map>
  5. #include <set>
  6. #include <unordered_set>
  7. #include <queue>
  8. #include <stack>
  9. #include <string>
  10. #include <climits>
  11. #include <algorithm>
  12. #include <sstream>
  13. #include <functional>
  14. #include <bitset>
  15. #include <numeric>
  16. #include <cmath>
  17. #include <regex>
  18. using namespace std;
  19. bool cmp(pair<int, int> a, pair<int, int> b)
  20. {
  21. return a.second >= b.second;
  22. }
  23. class Solution
  24. {
  25. public:
  26. vector<int> topKFrequent(vector<int>& nums, int k)
  27. {
  28. map<int, int> mmp;
  29. for (int i : nums)
  30. mmp[i]++;
  31. vector<pair<int, int>> all;
  32. for (auto i : mmp)
  33. all.push_back({ i.first,i.second });
  34. sort(all.begin(), all.end(), cmp);
  35. vector<int> res;
  36. for (int i = 0; i < k; i++)
  37. res.push_back(all[i].first);
  38. return res;
  39. }
  40. };

发表评论

表情:
评论列表 (有 0 条评论,245人围观)

还没有评论,来说两句吧...

相关阅读