p347

发表于 | 分类于 |

LeetCode 347 Top K Frequent Elements 题解

1.题目：

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].

题意：

给一个数组，返回这个数组重复出现次数最多的前k个数。

2.解题思路:

见代码：先用HashMap 对数组进行存储，再从大到小排序，取前K个。

3.代码

[title] [] [url] [link text]
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
 

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> ans = new ArrayList<Integer>();
		HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
		List<Map.Entry<Integer, Integer>> mHashMapEntryList;
		for (int i = 0; i < nums.length; i++) {
			if (hashMap.containsKey(nums[i])) {
				hashMap.put(nums[i], hashMap.get(nums[i]) + 1);
			} else {
				hashMap.put(nums[i], 1);
			}

		}
		mHashMapEntryList = new ArrayList<Map.Entry<Integer, Integer>>(
				hashMap.entrySet());
		Collections.sort(mHashMapEntryList,
				new Comparator<Map.Entry<Integer, Integer>>() {

					@Override
					public int compare(
							Map.Entry<Integer, Integer> firstMapEntry,
							Map.Entry<Integer, Integer> secondMapEntry) {
						return secondMapEntry.getValue().compareTo(
								firstMapEntry.getValue());//从大到小排序
					}
				});
		for (int i = 0; i < k; i++) {
			ans.add(mHashMapEntryList.get(i).getKey());
		}
		return ans;
    }
}

4.一些总结：