LeetCode347——优先队列解决查询前k高频率数字问题

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

例如，

给定数组 [1,1,1,2,2,3] , 和 k = 2，返回 [1,2]。

注意：

你可以假设给定的 k 总是合理的，1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

这里已经明确的要求了时间复杂度，那么对于这种前k个元素问题，可以采用小根堆结构来解决，因为把元素变为了树状结构，所以在时间复杂度方面绝对是优于扫描数组的，定义一个优先队列（jdk提供的优先队列是由小根堆实现的，这里正好符合要求），队列允许存储元素k个。

代码如下：

class Solution {

    private class Freq implements Comparable<Freq> {

		public int data, freq;

		public Freq(int data, int freq) {

			this.data = data;

			this.freq = freq;

		}

		@Override

		public int compareTo(Freq o) {

			if (this.freq > o.freq) {

				// 当前key的频率大于父节点的频率的话，不上浮

				return 1;

			} else if (this.freq < o.freq) {

				return -1;

			} else {

				return 0;

			}

		}

	}

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

		TreeMap<Integer, Integer> map = new TreeMap<>();

		// O(n)

		for (int num : nums) {

			if (map.containsKey(num)) {

				map.put(num, map.get(num) + 1);

			} else {

				map.put(num, 1);

			}

		}

		PriorityQueue<Freq> queue = new PriorityQueue<>();

		for (int key : map.keySet()) {

			if (queue.size() < k) {

				queue.add(new Freq(key, map.get(key)));

			} else if (map.get(key) > queue.peek().freq) {

				// 大于优先队列的最小值

				// 删掉最小值，并把当前的key加入优先队列

				queue.remove();

				queue.add(new Freq(key, map.get(key)));

			}

		}

		List<Integer> list = new ArrayList<>();

		while (queue.size() > 0) {

			Freq freq = queue.remove();

			list.add(freq.data);

		}

		return list;

	}

}

巴特西

LeetCode347——优先队列解决查询前k高频率数字问题

最新文章

热门文章