MajorityElementOPT2 [source code]

public class MajorityElementOPT2 {
    public int majorityElement(int[] nums) {
        int cnt = 0, curr = nums[0];
        for (int num : nums) {
            if (num == curr) {
                cnt++;
            } else if (cnt-- == 0) {
                curr = num;
                cnt = 1;
            }
        }
        return curr;
    }
}

这个也是一个 submission 最优解, 2ms. 这个做法好像叫moore voting.
这个算法也是在保证 linear 的同时, 做到了O(1) space;

这个是 discussion 里面别人总结的几个解:

// Sorting  
public int majorityElement1(int[] nums) {  
    Arrays.sort(nums);  
    return nums[nums.length/2];  
}  

// Hashtable   
public int majorityElement2(int[] nums) {  
    Map<Integer, Integer> myMap = new HashMap<Integer, Integer>();  
    //Hashtable<Integer, Integer> myMap = new Hashtable<Integer, Integer>();  
    int ret=0;  
    for (int num: nums) {  
        if (!myMap.containsKey(num))  
            myMap.put(num, 1);  
        else  
            myMap.put(num, myMap.get(num)+1);  
        if (myMap.get(num)>nums.length/2) {  
            ret = num;  
            break;  
        }  
    }  
    return ret;  
}  

// Moore voting algorithm  
public int majorityElement3(int[] nums) {  
    int count=0, ret = 0;  
    for (int num: nums) {  
        if (count==0)  
            ret = num;  
        if (num!=ret)  
            count--;  
        else  
            count++;  
    }  
    return ret;  
}  

// Bit manipulation   
public int majorityElement(int[] nums) {  
    int[] bit = new int[32];  
    for (int num: nums)  
        for (int i=0; i<32; i++)   
            if ((num>>(31-i) & 1) == 1)  
                bit[i]++;  
    int ret=0;  
    for (int i=0; i<32; i++) {  
        bit[i]=bit[i]>nums.length/2?1:0;  
        ret += bit[i]*(1<<(31-i));  
    }  
    return ret;  
}

Moore Voting是一个很聪明的算法, 这里是发明者自己给的一个动画: (http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html)

如果不确定确实有 majority 的话, 最后要加一个1pass 来确定最后得到的结果是 majority.

这个算法的聪明之处在于认为每一个 maj 以外的 candidate 都是一个敌对票, 所以最后能够用自己的+票来抵消所有其他对手的-票的, 肯定就是 majority 了;

这个bit manipulation的方法一开始没有看懂, 后来就懂了, 还算是一个很聪明的方法, 对每一个 bit 位分别进行 count, 因为每一个 bit 的 domain 只有2, 所以统计起来很方便, 不需要用 map 这么复杂的概念来设计.

Problem Description

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:46.19%
Contributor: LeetCode
Companies
adobe zenefits
Related Topics
array divide and conquer bit manipulation
Similar Questions
Majority Element II