LeetCode 347 Top K Frequent Elements

LeetCode 347 Top K Frequent Elements

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

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.

题目大意：

给定一个非空整数数组，返回其前k个出现次数最多的元素。

注意：
你可以假设k总是有效的，1 ≤ k ≤ 独立元素的个数。
你的算法时间复杂度必须优于O(n log n)，其中n是数组的长度。

解题思路：

这是经典题，解法是HeapSelect：求最大k个数，就先对前k个元素建最小堆，然后遍历k到最后一个数，若它大于栈顶就替换且做minHeapify。最后结果是
最大的k个数在数组的前k个位置且堆顶（数组第一个数）为k个数的最小。堆并没有排序。
结果并不需要从大到小输出。

统计词频
建key-value数组
heapSelect
把数组前k个数加入到结果集中

注意事项：

如果需要按大到小输出结果，需要对result进行排序O(klogk)，数组第一个也就是最小堆堆顶是这k个数中最小。
key-pair版堆选择算法。

Python代码：

from heapq import heapreplace, heappush

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	dict = {}
	for i in range(len(nums)):
		if nums[i] not in dict:
			dict[nums[i]] = 1
		else:
			dict[nums[i]] += 1

	freq_dict = [(v, k) for k, v in dict.items()]
	res = []
	for i in range(len(freq_dict)):
		if i < k:
			heappush(res, freq_dict[i])
		elif freq_dict[i][0] > res[0][0]:
			heapreplace(res, freq_dict[i])

	return [v for k, v in res]

统计词频部分可以用Counter优化。freq_dict有两个作用：将key和频率互换，还可以将dict转换成list方便和k比较

from heapq import heapreplace, heappush
from collections import Counter

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	dict = Counter(nums)
	freq_dict = [(v, k) for k, v in dict.items()]
	res = []
	for i in range(len(freq_dict)):
		if i < k:
			heappush(res, freq_dict[i])
		elif freq_dict[i][0] > res[0][0]:
			heapreplace(res, freq_dict[i])

	return [v for k, v in res]

Java代码：

public List<Integer> topKFrequent(int[] nums, int k) {
	List<Integer> result = new ArrayList<Integer>();
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	for(int i=0;i<nums.length;i++){
		if(map.containsKey(nums[i]))
			map.put(nums[i], map.get(nums[i])+1);
		else
			map.put(nums[i], 1);
	}
	Node[] f = new Node[map.size()];
	Iterator it = map.entrySet().iterator();
	int j=0;
	while(it.hasNext()){
		Map.Entry pair = (Map.Entry)it.next();
		Node node = new Node((int)pair.getKey(), (int)pair.getValue());
		f[j++] = node;
	}
	hselect(f, k);
	for(int i=0;i<k;i++)
		result.add(f[i].key);
	return result;
}
  
public void hselect(Node a[], int k){
	// min heap with size=k
	for (int i = k / 2; i >= 0; i--) {
		minHeapify(a, i, k);
	}
	for (int i = k; i < a.length; i++) {
		if (a[i].value > a[0].value) {
			swap(a, i, 0);
			minHeapify(a, 0, k);
		}
	}
}

public void minHeapify(Node[] arr, int i, int n) {
	int smallest = i;
	int l = left(i);
	int r = l + 1;
	if (l < n && arr[l].key < arr[smallest].key)
		smallest = l;
	if (r < n && arr[r].key < arr[smallest].key)
		smallest = r;
	if (smallest != i) {
		swap(arr, i, smallest);
		minHeapify(arr, smallest, n);
	}
}

private int left(int i) {
	return 2 * i + 1;
}

private void swap(Node[] arr, int index1, int index2) {
	Node tmp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = tmp;
}

class Node {
	int key;
	int value;
	public Node(int k, int v){
		key = k;
		value = v;
	}
	
	public String toString(){
		return "("+key+","+value+")";
	}
}

算法分析：

时间复杂度为O(nlogk)，空间复杂度O(1)。时间复杂度是O(n)+O(nlogk),空间复杂度为O(m)+O(1),m为不重复的元素个数(unique element)。

算法II解题思路：

此题关于数组频数，所以考虑用桶排序(bucket sort)

统计词频（元素->频数）
桶排序：n+1个桶（n为原数组大小），把元素放入频数对应的桶号（频数->元素），用List把这些元素串起来。
逆序（从大到小）遍历不为空的桶，输入结果直至k个。
与上面算法不同的是结果是从大到小输出。数据类型有两个HashMap存储元素对应的频数，而List数组List[]反过来存储频数对应的元素。

注意事项：

桶排序要用List串联起元素，例如[1,2],k=2，频数为1的元素有两个，所以桶的内容应该是List。Python用[[] for _ in range(len(nums) + 1)]
桶数量为原数组大小+1，例如一个元素[1], 它的频数为1，而频数为0是不会出现。
逆序遍历所有桶，只要结果集个数为k，就停止循环。

Python代码：

from collections import Counter

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	di = Counter(nums)
	freq = [[] for _ in range(len(nums) + 1)]
	for key, val in di.items():
		freq[val].append(key)
	res = []
	for i in range(len(freq) - 1, 0, -1):
		for n in freq[i]:
			if k > 0:
				res.append(n)
				k -= 1
	return res

Java代码：

public List<Integer> topKFrequent2(int[] nums, int k) {
	 List<Integer> result = new ArrayList<Integer>();
	 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	 for(int i=0;i<nums.length;i++){
		if(map.containsKey(nums[i]))
			map.put(nums[i], map.get(nums[i])+1);
		else
			map.put(nums[i], 1);
	 }
	 List<Integer>[] f = new List[nums.length+1];
	 Iterator it = map.entrySet().iterator();
	 while(it.hasNext()){
		 Map.Entry pair = (Map.Entry)it.next();
		 if(f[(int)pair.getValue()]==null)
			 f[(int)pair.getValue()] = new ArrayList();
		 f[(int)pair.getValue()].add((int)pair.getKey());
	 }
	 for(int i=f.length-1;i>0 && result.size()<k;i--)
		 if(f[i]!=null){
			 result.addAll(f[i]);
		 }
	 return result;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。时间复杂度是O(n)+O(n),空间复杂度为O(m)+O(n),m为不重复的元素个数(unique element)。

Follow-up:

题目可以包装成：给定一个文档，返回其前k个出现次数最多的单词。
Given a document, return the k most frequent words. Assume punctuation are removed.
Given a non-empty array of strings, return the k most frequent elements.
如果写出了桶排序，可以考虑假设机器memory有限，只够O(m)，不能一次性读出整个文档，也就是不能用桶排序，只能用堆选择。
如果写出了堆选择，可以考虑k比较大，如果进一步提高时间复杂度，也就是只能O(n),符合这个要求就只有计数排序，基数排序和桶排序。

这是priorityQueue实现的Heap（对于基本数据类型默认是最小堆，但由于Node是自定义，必须实现Comparator），由于PQ需要额外空间，所以
较少用。

Java代码：

public List<Integer> topKFrequent3(int[] nums, int k) {
	 List<Integer> result = new ArrayList<Integer>();
	 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	 for(int i=0;i<nums.length;i++){
		if(map.containsKey(nums[i]))
			map.put(nums[i], map.get(nums[i])+1);
		else
			map.put(nums[i], 1);
	 }
	 Node[] f = new Node[map.size()];
	 Iterator it = map.entrySet().iterator();
	 int j=0;
	 while(it.hasNext()){
		Map.Entry pair = (Map.Entry)it.next();
		Node node = new Node((int)pair.getKey(), (int)pair.getValue());
		f[j++] = node;
	 }
	 
	 PriorityQueue<Node> minHeap = new PriorityQueue<Node>(k,
			new Comparator<Node>() {
				@Override
				public int compare(Node o1, Node o2) {
					return o1.value - o2.value;
				}
			}
	);

	for (int i = 0; i < f.length; i++) {
		if (i < k) {
			minHeap.offer(f[i]);
		} 
		else {
			Node minNode = minHeap.peek();
			if (f[i].value > minNode.value) {
				minHeap.poll();
				minHeap.offer(f[i]);
			}
		}
	}

	while(!minHeap.isEmpty())
		result.add(minHeap.poll().key);
	return result;
 }