https://leetcode.com/problems/majority-element/#/description

挑出多余n/2 的元素，这个题有很多答案。

1. hash 表计数，这个不用说。

2. 排序然后线性扫一遍这个要nlogn。

3. divide & conqur. 这个不太理解-_-

4.majority vote 这个就比较厉害了，只用O(n) 的时间和O(1) 的空间。

5. 位投票，不知道这个点子是怎么被想出来的，非常有趣。

majority vote：http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

流程就是，一个变量t 作为当前投票最多的candidate，另一个变量n 是他的投票数。遍历数组，如果num[i] == t 就n++ 否则就n--。如果n ==0 那么t 就下台，换下一个candidate

这样可以证明当i == array.length 的时候，t 是major，iff 存在major。因为n 是count(major) - count(other) 如果major 存在那么肯定大于0，而n >0 的那个必定是major。

var majorityElement = function(nums) {    var major = nums[0];    var count = 1;    for (var i = 1; i < nums.length; i++) {        if (count === 0) {            major = nums[i];            count = 1;        } else if (nums[i] !== major) {            count--;        } else {            count++;        }    }    return major;};

另一个位投票的方法也很厉害，假设数组元素是32 位整型，那么我们就生成32 个mask，第i 个mask 的第i 位是1，其余位都是0。

形式如同：

0: 0001

1: 0010

2: 0100

。。。。

然后对于每个mask，用数组里的每个元素做& 操作，如果结果不为0，则对与这个mask 来说，它的投票加一，当数组遍历完如果票数>n/2 就说明major 的这个位为1。所以 major |= mask

这样等32 个mask 都投完票以后major 也组装完毕了

    var mask = 1;    var len = nums.length;    var major = 0;    var majors =[];    for (var i = 0, mask = 1; i < 32; i++, mask <<= 1) {        var count = 0;        for (var j = 0; j < len; j++) {            if (mask & nums[j]) {                count++;            }            if (count > len / 2) {                major |= mask;                break;            }        }    }    return major;

Majority Element