347.Top K Frequent Elements

tags: Medium,Array,Hash Table,Heap,Divide and Conquer,Sorting

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.

範例

Example 1:

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

Example 2:

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

Constraints:

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

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

解答

Javascript

function topKfrequent(nums, k) {
  const map = new Map();
  for (const num of nums) {
    map.set(num, map.get(num) + 1 || 1);
  }

  // sort
  const sorted = [...map.entries()].sort((a, b) => b[1] - a[1]);
  const result = [];
  for (let i = 0; i < k; i++) {
    result.push(sorted[i][0]);
  }

  return result;
}

MarsgoatMay 22, 2023

TypeScript

function topKFrequent(nums: number[], k: number): number[] {
  const map = new Map<number, number>();

  nums.forEach((num) => map.set(num, (map.get(num) || 0) + 1));

  const sortedArr = [...map.entries()].sort((a, b) => b[1] - a[1]);
  
  // 這樣慢一點 但是可以一行
  return sortedArr.slice(0, k).map((num) => num[0]);
}

SheepMay 22, 2023

Python

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        if len(nums) == k: return nums
        counter = Counter(nums)

        # Max heap
        heap = [(-freq, num) for num, freq in counter.items()]
        heapq.heapify(heap)
        
        ans = []
        for _ in range(k):
            ans.append(heapq.heappop(heap)[1])

        return ans

看了題解發現可以縮

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]: 
        if k == len(nums): return nums
        counter = Counter(nums)   

        return heapq.nlargest(k, counter.keys(), key=counter.get)

TC:

$O(nlogk)$
SC:

$O(n)$

Ron ChenMon, May 22, 2023

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return [n for n, _ in Counter(nums).most_common(k)]

Yen-Chi ChenMon, May 22, 2023

Reference

回到題目列表