[LeetCode] - Java - top K high frequency elements

Topic Description: given a non empty array of integers, return the elements with a higher frequency than k.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
 Output: [1,2]

Example 2:

Input: nums = [1], k = 1
 Output: [1]

Explain:

  • You can assume that the given k is always reasonable, and 1 ≤ k ≤ the number of different elements in the array.
  • The time complexity of your algorithm must be better than O(n log n), where n is the size of the array.

Solution 1: using priority queue, first get the number of occurrences of each element, and then add it to the priority queue according to the number of occurrences. Queue k times in turn is the required solution. My code is as follows:

public class TopKFrequent {
	public List<Integer> topKFrequent(int[] nums, int k) {
		List<Integer> list = new ArrayList<>();

		// Define a priority queue first
		PriorityQueue<Entry<Integer, Integer>> queue = new PriorityQueue<>(new Comparator<Entry<Integer, Integer>>() {
			@Override
			public int compare(Entry<Integer, Integer> o1, Entry<Integer, Integer> o2) {

				return o2.getValue() - o1.getValue();
			}
		});

		// Get the number of occurrences of each element
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
		}

		// Join queue
		for (Entry<Integer, Integer> entry : map.entrySet())
			queue.add(entry);

		// Team K times
		for (int i = 0; i < k; i++)
			list.add(queue.poll().getKey());

		return list;
	}
}

Method 2: first, use HashMap to store the number of occurrences of each element, define n+1 buckets, map the number of occurrences to buckets, use zipper method to solve conflicts, traverse buckets in reverse order, when the number of elements found is equal to K, it is the required result, such as nums = {1,1,2,2,3}, when k is equal to 2, the figure is as follows

The result of map: 1-2, 2-2, 3-1, define 6 buckets, mark the sequence number as 0-5, element 1 appears twice, element 2 appears twice, element 3 appears once, map to the bucket, as shown below,

0        1         2         3         4         5 

          3         1

                     2

Traverse bucket in reverse order, terminate when the number of res is greater than k,

My code is as follows

public class TopKFrequent {
	public List<Integer> topKFrequent(int[] nums, int k) {

		// Define a bucket
		ArrayList<Integer>[] bucket = new ArrayList[nums.length + 1];

		// Get the number of occurrences of each element
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
		}

		for (Integer n : map.keySet()) {
			Integer value = map.get(n);
			if (bucket[value] == null) {
				ArrayList<Integer> list = new ArrayList();
				bucket[value] = list;
			}
			bucket[value].add(n);
		}
		List<Integer> res = new ArrayList<>();
		for (int i = nums.length; i >= 0 && res.size() < k; i--) {
			if (bucket[i] != null) {
				res.addAll(bucket[i]);
			}
		}
		return res;
	}
}

Reference resources: https://leetcode-cn.com/problems/top-k-frequent-elements/comments/

Posted on Sat, 09 Nov 2019 08:03:14 -0800 by huntrguy102