动易网站后台管理功能,国家企业信息网官网,网站推广互联网推广,无锡网站制作公司排名给定一个非空的整数数组#xff0c;返回其中出现频率前 k 高的元素。
示例 1:
输入: nums [1,1,1,2,2,3], k 2 输出: [1,2] 示例 2:
输入: nums [1], k 1 输出: [1] 说明#xff1a;
你可以假设给定的 k 总是合理的#xff0c;且 1 ≤ k ≤ 数组中不相同的元素的个数…给定一个非空的整数数组返回其中出现频率前 k 高的元素。
示例 1:
输入: nums [1,1,1,2,2,3], k 2 输出: [1,2] 示例 2:
输入: nums [1], k 1 输出: [1] 说明
你可以假设给定的 k 总是合理的且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
思路把数字与对应的个数存入哈希表排序
提交的代码
class Solution { public static ListInteger topKFrequent(int[] nums, int k) { MapInteger,Integer map new HashMap(); ListInteger result new ArrayListInteger(); for(int i0;inums.length;i) { if(map.containsKey(nums[i])) { map.put(nums[i], map.get(nums[i])1); } else { map.put(nums[i], 1); } } ListMap.EntryInteger, Integer entryList new ArrayListMap.EntryInteger, Integer(map.entrySet()); Collections.sort(entryList, mapComparator); int j 0; for (Map.EntryInteger, Integer entry : entryList) { if (j k) { break; } result.add(entry.getKey()); j; } return result; } static ComparatorMap.EntryInteger, Integer mapComparator new ComparatorMap.EntryInteger, Integer() { Override public int compare(Map.EntryInteger, Integer item1, Map.EntryInteger, Integer item2) { return item2.getValue() - item1.getValue(); } };
}
