leetcode day 16: majority element

Given an array of n integers, find the majority element (the element whose count is >= [ n / 2]).

Count means map.

func majorityElement(nums []int) int {
    // Count means map.
    counts := map[int]int{}
    for _,v := range(nums) {
        counts[v]++
    }
    targetCount := len(nums) / 2
    currentMaxCount := 0
    target := -9999999999
    for k,v := range(counts) {
        if v > targetCount && v > currentMaxCount {
            currentMaxCount = v
            target = k
        }
    }
    return target
}

Scored top 90% on time, top 40% on memory. But if you know the trick (Moore’s candidate algorithm)…

func majorityElement(nums []int) int {
    // "If you know the trick"...Moore's voting algorithm
    count := 0
    var target int
    for i := 0; i < len(nums); i++ {
        if count == 0 {
            target = nums[i]
            count++
        } else if nums[i] == target {
            count++
        } else {
            count--
        }
    }
    return target
}

Gets us to 94% time, 71% memory. Using range() causes Go to use more memory (drops to 19%!).

The “best” algorithm is not that much better, so I’ll call my solution good.