【leetcode】169. Majority Element

题目

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋times.

You may assume that the array is non-empty and the majority element always exist in the array.

分析

给定一个数组长度为n，其中有一个元素出现的次数大于⌊ n/2 ⌋，现在我们要找出这个元素

moore-voting算法

主要思想

找出一对不同的元素就去掉它们，最后剩下的一定是所找的元素。

需要两个指针和一个计数器，其中一个指针指向当前出现次数最大的元素，另一个向后遍历，count存储当前出现次数最大的元素出现的次数

当用于遍历的指针2指向元素和指针1指向的元素相等时，count加1，否则减1
当count减至0的时候，指针1需要向后移动到指针2的位置，指针2继续向后遍历

代码

int majorityElement(vector<int>& nums) {
    int len = nums.size();
    int result = 0;
    int count = 1;
    int temp = 0;
    for (int i = 1; i < len; i++) {
        if (count != 0) {
            if (nums[i] == nums[temp])
                count++;
            else
                count--;
        }
        else {
            temp = i;
            count = 1;
        }       
    }
    return nums[temp];
}

结果

bit manipulation

主要思想

把数字都转化为二进制处理。如果majority element第i位上的数字是1，那么所有数字第i位上为1的总个数一定会大于⌊ n/2 ⌋,反之，如果majority element第i位上的数字是0，那么所有数字第i位上为0的总个数一定会大于⌊ n/2 ⌋

所以，如果我们统计所有的n个数字的第i位上1(或者0)的个数，看是否大于⌊ n/2 ⌋，就可以确定majority element第i位到底是0还是1了

int型数据一共有32bit，所有需要计算32个二进制位。

代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int i,j,count,major=0;
        for(i=0;i<32;i++)
        {
            for(j=0,count=0;j<nums.size();j++)
            {
                if((nums[j]>>i&1)==1)
                    count++;
            }
            if(count>nums.size()/2)
                major+=(1<<i);
        }
        return major;
    }
};

结果

问题

在用bit manipulation方法时，在已经确定了定majority element第i位到底是0还是1之后恢复majority element的时候，遇到了一个问题，查了很久，在这里总结一下

一开始我用了下面这样的方法恢复majority element

for (int i = 0; i < 32; i++) {
    if (countones[i] > len / 2)
        result += pow(2, i);
}

就是我们平时手算二进制转化成10进制的方法，但是发现遇到负数的时候就不能正确恢复了==

然后就查啊查，发现：

int类型默认是signed的，也就是说带符号的，32bit中最高的那一位是用来表示符号的，最高位是0表示非负数，最高位是1表示负数，所以能够表示的整数的范围是$-2^{31}-1$~$2^{31}-1$。关于负数的二进制表示，之前写过一篇博客负数的二进制表示，可以看出来确实负数的二进制表示最高位是1

所以用上面的方法不断叠加$2^i$（正数）是永远都不会恢复到原来的负数的，因为最高位永远都不会由0变为1，而且$2^{31}$已经超过int型的表示范围了。

因此，还是要用bit运算根据各个位是0还是1来恢复出原来的majority element，这样无论是正是负就都不会出错了。