347.Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

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

Example 2:

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

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.
• It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
• You can return the answer in any order.

Analyze

思路一:

1. 将各个元素出现的频率统计进哈希表中;
2. 然后对出现频率进行排序;
3. 取频率排前 k 的元素;

这样的时间复杂度为 O(nlog n) 级别。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
  const obj = {}
  for (let i = 0; i < nums.length; i++) {
    if (!obj[nums[i]]) {
      obj[nums[i]] = 1
    } else {
      obj[nums[i]] = obj[nums[i]] + 1
    }
  }

  const list = []

  const keysArr = Object.keys(obj)
  for (let i = 0; i < keysArr.length; i++) {
    const key = keysArr[i]
    const value = obj[key]
    list.push({ key, value })
  }

  list.sort((r1, r2) => r2.value - r1.value)
  const result = []
  list.map((obj, index) => {
    if (index < k) {
      result.push(parseInt(obj.key, 10))
    }
  })
  return result
}

该题解虽然可以 ac, 但是由于题目给出了时间复杂度需小于 (n log n) 这一限制, 因而我们思考其它方式🤔。

思路二: 桶排序分组的思想

1. 首先将各个元素出现的频率统计进哈希表中;
2. 将频率减去 1 后的值作为数组 list 的下标存入;
3. 从 list 中遍历取出频率最高的 k 个元素;

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
  const obj = {}
  for (let i = 0; i < nums.length; i++) {
    if (!obj[nums[i]]) {
      obj[nums[i]] = 1
    } else {
      obj[nums[i]] = obj[nums[i]] + 1
    }
  }

  const list = []

  const keysArr = Object.keys(obj)
  for (let i = 0; i < keysArr.length; i++) {
    const key = keysArr[i]
    const value = obj[key]
    if (!list[value - 1]) {
      list[value - 1] = [parseInt(key, 10)]
    } else {
      list[value - 1].push(parseInt(key, 10))
    }
  }

  const result = []
  let count = 0
  for (let i = list.length - 1; i >= 0; i--) {
    const curList = list[i]
    if (curList) {
      for (let x = 0; x < curList.length; x++) {
        if (count === k) return result
        result.push(curList[x])
        count++
      }
    }
  }
  return result
}