首页 > 代码库 > Majority Element

Majority Element

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