[LeetCode] Majority Element - (Kotlin)

https://leetcode.com/problems/majority-element

Majority Element - LeetCode

 

정수 배열에서 가장 많이 나타난 수를 찾는 문제이다. 언듯 보기에는 쉬워보이지만, 문제 조건에 시간복잡도 O(N), 공간복잡도 O(1) 조건이 있었다.
위 조건을 무시하고 코틀린의 메서드를 이용하여 해결한 방법, 다른 풀이를 참고하여 조건을 만족하도록 해결한 방법이 있다.

조건 무시

fun majorityElement(nums: IntArray): Int {
    return nums.groupBy { it }
               .map { it.key to it.value.size }
               .sortedByDescending { it.second }[0]
               .first
}

조건 만족 (시간복잡도 O(N), 공간복잡도 O(1))

fun majorityElement1(nums: IntArray): Int {
    var n = 0
    var cnt = 0

    for (i in nums) {
        if (cnt == 0) {
            n = i
        }
        if (i == n) {
            cnt++
        } else {
            cnt--
        }
    }

    return n
}