With and without using bit manipulation


  • 0
    M
    1. The first way is to perform bit manipulation on the array of integers. The whole idea is to construct the majority element by setting up the bit in the correct position, so we need to traverse 'n' times for every bit to be set in the result.
      Algorithm:
    • For each bit position, count the majority bit by traversing the entire array. When we have additional info such as which bit '1' or '0' occurred more times at a position, then the majority element should have that bit to be set at that position.
      The code is intuitive:
         public int majorityElement(int[] nums)
         {
             int result = 0, mask = 1, count = 0, size = nums.length;
             for( int bitIndex = 0; bitIndex < 32; bitIndex++ )
             {
                 count = 0;
                 for( int index = 0; index < size; index++ )
                 {
                     if( (nums[index] & mask) != 0 )
                        count++;
                 }
                 if( count > (size / 2) )
                    result |= mask;
                if( bitIndex  != 31 )
                    mask <<= 1;
             }
             return result;
         }
    }
    
    1. The second way is to use the famous Moore voting algorithm whose basic idea is, if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till the end if it is a majority element.
    public int majorityElement(int[] nums) {
            int majorityElem = nums[0], count = 1;
            for( int i = 1; i < nums.length; i++ )
            {
                if( count == 0 )
                {
                    majorityElem = nums[i];
                    count = 1;
                }
                else
                {
                    if( nums[i] == majorityElem )
                        count++;
                    else
                        count--;
                }
            }
            return majorityElem;
        }
    

    Thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.