【LeetCode】多数元素

题目链接：https://leetcode.cn/leetbook/read/top-interview-questions/xm77tm/
题目描述：

这题如果无时间复杂度和空间复杂度限制则解法比较容易想到，不外乎几种：map记录次数、排序后取中间的（因为排序后最多的元素超过一半的中间的元素肯定也是答案），但是时间和空间后就不得不另想其它解法了，下面是两种能想到的解法。

方法1：消除法

利用两个元素维护答案，其中res维护的是当前次数最多的元素，cnt维护出现的次数，向后遍历过程中，如果当前元素和res相等，直接cnt++，否则cnt–，此时注意cnt为0时更新一下res。

func majorityElement(nums []int) int {
    res := nums[0] //当前次数最多的元素
    cnt := 1 // 当前次数
    for i := 1; i < len(nums); i++ {
        if nums[i] == res {
            cnt++
        } else {
            cnt--
            if cnt == 0 {
                cnt = 1
                res = nums[i]
            }
        }
    }
    return res 
}

方法2：位运算

位运算思想比较简单，一个32位的int值，统计该数组中每一位为1的次数，如果某一位出现的1的次数超过了数组的一半大小，将其计入答案中即可。

func majorityElement(nums []int) int {
    res := 0 
    // 遍历32位，对每一位进行检查
    for i,mask := 0,1; i < 32; i,mask = i+1,mask<<1 {
        cnt := 0 // 记录当前该位为1的次数
        for j := 0; j < len(nums); j++ {
            if (nums[j] & mask) == mask { // 当前这位为1
                cnt++
            }
            // 计入答案
            if cnt > len(nums)/2 {
                res |= mask
                break
            }
        }
    }
    return res 
}