169.majority-element.md

169. Majority Element

Hash Table

fun majorityElement(nums: IntArray): Int {
    val count = hashMapOf<Int, Int>()
    for (num in nums) {
        count[num] = (count[num] ?: 0) + 1
        if (count[num]!! > nums.size / 2) return num
    }
    return 0
}

• Time Complexity: O(n).
• Space Complexity: O(n).

Sorting

fun majorityElement(nums: IntArray): Int {
    nums.sort()
    return nums[nums.size / 2]
}

• Time Complexity: O(n lg n).
• Space Complexity: O(lg n).

Moore Vote Algorithm

Suppose we have a, b two elements and the number of a is more than b by 1, i.e. [a, b, a, a, b]. Then we keep find the distinct pair and remove them, the last remaining element is the result.

Remove the first pair (a, b) => [a, a, b]
Remove the second pair (a, b) => [a]

The answer is `a`

fun majorityElement(nums: IntArray): Int {
    var count = 0
    var majority = 0
    for (i in 0 until nums.size) {
        if (count == 0) {
            majority = nums[i]
        }
        if (nums[i] == majority) {
            count++
        } else {
            count--
        }
    }
    return majority
}

• Time Complexity: O(n).
• Space Complexity: O(1).