347. Top K Frequent Elements [Medium]

347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Example

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

思路

• 第一步，看到频率，那就是要统计出现次数，统计次数就要联想到HashMap，那现在已经有了一个存放数组中每个值出现次数的HashMap。

• 第二部，就是如何取出k个value值频率最大的key数组元素并把它放入结果类型int[]中

  • 借用桶排序的思想，可以先new一个数组用来存放全部结果，把数组的下标当作出现的频率，数组里的值存放该频率的数组元素
  • 可以确定的是，该结果数组长度最大不会超过nums的长度， 极端情况nums全部都是同一个值，那结果数组无非是给最后一个下标赋值。这里注意最大不会超过nums长度，所以等于nums. length+1，下标0要占一位

• 第三步，直接从后往前遍历结果数组，因为下标越大，代表频率越高，取出k个塞到int[]里完事

题解

    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> recordMap = new HashMap<>();
        List<Integer>[] totalRes = new List[nums.length];
        int[] result = new int[k];

	// 第一步，用HashMap来存放每个值的出现频率
        // O(n)
        for (int val : nums)
            recordMap.put(val, recordMap.getOrDefault(val, 0) + 1);
	// 第二部，把出现频率也是value当作数组下标，把key也就是数组元素作为值，塞到结果数组里
        // O(n)
        recordMap.forEach((key, val) -> {
            if (totalRes[val] == null)
                totalRes[val] = new ArrayList<>(Arrays.asList(key));
            else
                totalRes[val].add(key);
        });

        for (int i = totalRes.length - 1; i >= 0; i--) {
            List<Integer> tmpRes = totalRes[i];
	    // 有可能该下标下没有值，要做判空
            if (tmpRes != null)
                for (Integer val : tmpRes) {
                    result[--k] = val;
                    if (k < 0)
                        return result;
                }

        }
        return result;
    }