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.

Solution 1:  sort and find the middle. O(nlogn) which is actually faster than Solution 2

 public class Solution {  
   public int majorityElement(int[] nums) {  
     Arrays.sort(nums);  
     return nums[nums.length/2];  
   }  
 }  

Solution 2:  bit count, O(n) which is not actually fast than solution 1. as logn normally will be less than 32.

 public class Solution {  
   public int majorityElement(int[] nums) {  
     int n=nums.length;  
     int[] count=new int[32];  
     for (int x: nums)  
       for (int i=0; i<32; i++)  
         if ((x>>i&1)==1) count[i]++;  
     int res=0;  
     for (int i=0; i<32; i++)  
       if (count[i]>n/2) res|=1<<i;  
     return res;  
   }  
 }