找出数组中出现次数最多的k个元素

发表于 | 分类于 | 阅读次数

题目：给一个非空数组，求数组中出现次数最多的k个元素。例如给出数组[1, 1, 1, 2, 2, 3]和k=2，返回[1, 2]

思路1

使用HashMap来对数组中的元素计数并存储，然后使用HashMap中的value构造大顶堆，取k次大顶堆的堆顶元素，同时调整大顶堆堆，取出value对应的key值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 // 使用HashMap+大顶堆来实现（取堆顶的最大k个元素）
public static List topKFrequent(int[] nums, int k) {
	Map<Integer, Integer> map = new HashMap<>();
	for (int i : nums) {
		map.put(i, map.containsKey(i) ? map.get(i) + 1 : 1);
	}
	// 使用java自带的PriorityQueue类来实现，PriorityQueue是优先队列，实际上是一个小顶堆
	PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue()); // 改变排序的方法，使用value作为判断
	pq.addAll(map.entrySet());
	List ret = new ArrayList<>();
	for (int i = 0; i < k; i++) {
		ret.add(pq.poll().getKey());// 每次都会去取堆顶的元素，每弹出一个元素都会重新调整堆
	}
	return ret;
}

时间复杂度O(N+klgk+(N-k)lgk) = O(Nlgk)，N：遍历数组，klgk：建堆，(N-k)lgk：剩余N-k个元素插入堆

思路二

使用桶排序的思想，将出现次数为count的元素放入bucket[count]中，然后从bucket的index从大到小遍历。（这里需要注意的是有些出现次数一样的元素，所以我们的bucket数组需要定义成集合数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 使用桶排序的思想
public static List topKFrequent2(int[] nums, int k) {
	List[] bucket = new ArrayList[nums.length + 1]; // 定义一个链表的数组，主要是为了解决一个频数出现多次的情况
	Map<Integer, Integer> map = new HashMap<>();
	for (int i : nums) {
		map.put(i, map.containsKey(i) ? map.get(i) + 1 : 1);
	}
	for (int key : map.keySet()) {
		int frequency = map.get(key);
		if (bucket[frequency] == null) {
			bucket[frequency] = new ArrayList<>();
		}
		bucket[frequency].add(key);
	}
	List ret = new ArrayList<>();
	for (int i = bucket.length - 1; i >= 0 && ret.size() < k; i--) {
		if (bucket[i] != null) {
			ret.addAll(bucket[i]);
		}
	}
	return ret;
}

时间复杂度O(n)空间换时间

Fork me on GitHub