💯 Daily LeetCode Challenge Day_17 - Top K Frequent Elements

Account Login - LeetCode

---

문제

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.

---

k번째까지 자주 나온 수를 return 해야 한다. [Int]

O(nlogn) 보다 time complexity 가 좋아야 한다.

return 되는 [Int] 의 순서는 상관없다.

Dictionary 가 O(1)의 시간복잡도를 가지니 써야겠다는 생각을 했다.

key는 숫자고 value는 빈도수이다.

nums 배열을 map을 통해 빈도 중복 상관없이 (nums[i],1) 의 튜플 배열을 만든다.

그리고 빈도수를 가지는 Dictionary를 만들기 위해 uniquingKeysWith를 사용한다.

uniquingKeysWith 를 사용해 같은 key를 가지면 해당 key의 value에 중복되는 key의 value를 더한다.

Apple Developer Documentation

오름차순으로 정렬한 뒤 k번째까지만 정답 배열에 담는다.

class Solution {
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        
        let tupleArray = nums.map { ($0 , 1)}
        let frequency = Dictionary(tupleArray, uniquingKeysWith: +)
        let sortedFrequency = frequency.sorted{$0.1 > $1.1}
        var counter = 0
        var answer : [Int] = []
        for (key,value) in sortedFrequency {
            if counter == k {
                break
            }
            answer.append(key)
            counter += 1
        }
        return answer
    }
}