169.md

majority element 多数元素

解法一

暴力解法（leetcode中超过了时间限制）

func majorityElement(nums []int) int {
    c := 0
    index := 0
    for i := 0;i < len(nums);i++ {
        count := 0
        for j := 0; j < len(nums);j++ {
            if nums[j] == nums[i] {
                count ++
            }
        }
        if count > c {
                c = count
                index = i
            }
    }
    return nums[index]
}

解法二

使用一个辅助的map

func majorityElement(nums []int) int {
    ma := map[int]int{}
    for _,v := range nums {
        ma[v]++
    }
    count := 0
    result := 0
    for k,v := range ma {
        if count < v {
            count = v
            result = k
        }
    }
    return result
}

解法三

排序

func majorityElement(nums []int) int {
    sort.Ints(nums)
    count := 1
    for k,v := range nums {
        if k >=1 {
            if v == nums[k-1]{
                count++
            }else {
                count = 1
            }
        }
        if count > len(nums)/2{
            return v
        }
    }
    return -1
}