[LeetCode][Kotlin] 169. Majority Element

169. Majority Element

Given an array nums of size n, return the majority element.

 

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

크기 n의 배열 num이 주어지면 대부분의 요소를 반환합니다. 

다수 요소는 ⌊n/2⌋회 이상 나타나는 요소입니다. 대부분의 요소가 배열에 항상 존재한다고 가정할 수 있습니다.

 

Example 1:

Input: nums = [3,2,3]

Output: 3

 

Example 2:

Input: nums = [2,2,1,1,1,2,2]

Output: 2

 

Constraints:

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

---

코드 1

• 배열 원소들의 개수를 세고, 개수에 대한 내림차순 정렬을 한다.
• 정렬한 리스트의 첫 번째 원소는 다수의 요소를 나타낸다.

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

        return hm.toList()
            .sortedByDescending { it.second }
            .let { it[0].first }
    }
}

 

코드 2 (보이어-무어 투표 알고리즘)

• answer = 다수 요소의 후보를 저장하는 변수
• count = 현재 후보의 빈도를 세기 위한 변수

class Solution {
    fun majorityElement(nums: IntArray): Int {
        var answer = 0
        var count = 0

        for (num in nums) {
            if (count == 0) {
                answer = num
            }
            count += if (num == answer) 1 else -1
        }

        return answer
    }
}

---

Boyer-Moore 과반수 투표 알고리즘