169. Majority Element Leetcode Java

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.

Solution:

1.Voting Algorithm

We maintain a vote counter for latest leading element, during the iteration of array, if the current element is not the leading element, we decrease the vote counter, if yes,increase it. If the vote counter becomes negative,which means the leading element is not the leader any more so we update the leading element. After the iteration, the majority element will definitely win the poll and be the leading element.

Runtime: O(n)

   public int majorityElement(int[] num) {  
    if(num==null) return 0;  
    int vote=1;  
    int res=num[0];  
    for(int i=1;i<num.length;i++){  
      if(num[i]==res) vote++;  
      else{  
        vote--;  
        if(vote<0){  
          res=num[i];  
          vote=1;  
        }  
      }  
    }  
    return res;  
   }  

2.Bit manipulation
We maintain a 32 digits int[] array and do the increment for each digit for each visited element. After the iteration, we check the digits array,and restore the number by looking up all digits that are larger than n/2.
Runtime: O(32*n)=O(n)

  public int majorityElement(int[] num) {  
    if(num==null || num.length==0) return 0;  
    int[] dig=new int[32];  
    for(int i=0; i<num.length;i++){  
      int temp=num[i];  
      for(int j=0;j<32;j++){  
        dig[j]+=temp & 1;  
        temp=temp>>1;  
      }  
    }  
    int count=num.length/2;  
    int res=0;  
    int temp=1;  
    for(int i=0;i<32;i++){  
      if(dig[i]>count) res=res|temp;  
      temp=temp<<1;  
    }  
    return res;  
   }