多数元素

题目描述：

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：[3,2,3]
输出：3
示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

进阶：

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题

思路:

用摩尔投票法，如果我们把众数记为 +1+1，把其他数记为 -1−1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

代码:

func majorityElement(nums []int) int {
    count := 1
    cantidate := nums[0]
    for i:=1  ;i<len(nums) ;i++{
        if nums[i] == cantidate{
            count ++
        }else{
            count --
        }
        if count == 0{
            count = 1
            cantidate = nums[i]
        }
    }
    return cantidate
}

代码效率：

执行用时：12 ms, 在所有 Go 提交中击败了98.28%的用户
内存消耗：5.9 MB, 在所有 Go 提交中击败了98.28%的用户