[LeetCode][Kotlin] 347. Top K Frequent Elements

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.

정수 배열 nums와 정수 k가 주어지면 가장 자주 사용되는 k개의 요소를 반환합니다. 어떤 순서로든 답변을 반환할 수 있습니다.

 

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^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.

---

코드 1

• 배열의 각 원소의 개수 세기
• 개수를 기준으로 내림차순 정렬

class Solution {
    fun topKFrequent(nums: IntArray, k: Int): IntArray {
        val hm = HashMap<Int, Int>()
        nums.forEach { hm[it] = hm.getOrDefault(it, 0) + 1 }

        val sortMap = hm.entries.sortedByDescending { it.value }
        val answer = mutableListOf<Int>()

        for ((i, v) in sortMap.withIndex()) {
            answer.add(v.key)

            if (i == k - 1) {
                break
            }
        }

        return answer.toIntArray()
    }
}

 

코드 2

• 배열의 각 원소의 개수 세기
• 원소가 가질 수 있는 개수는 배열의 크기를 넘지 않기 때문에 빈도를 체크하기 위한 새로운 배열(freq)을 nums 의 크기만큼 만든다.
• 새로운 배열(freq)의 인덱스는 원소의 개수로, 해당 원소를 새로운 배열(freq)에 추가한다.
• 가장 많은 개수를 가진 원소는 뒤에서부터 배치되어 있기 때문에 역순으로 확인한다.

class Solution {
    fun topKFrequent(nums: IntArray, k: Int): IntArray {
        val hm = HashMap<Int, Int>()
        nums.forEach { hm[it] = hm.getOrDefault(it, 0) + 1 }

        val freq = MutableList(nums.size + 1) { mutableListOf<Int>() }
        for ((k, v) in hm) {
            freq[v].add(k)
        }

        val answer = mutableListOf<Int>()
        for (i in freq.lastIndex downTo 0) {
            for (n in freq[i]) {
                answer.add(n)
                if (answer.size == k) {
                    return answer.toIntArray()
                }
            }
        }

        return intArrayOf()
    }
}