[Duplicate][Divide and Conquer][Bit Manipulation]Majority Element

1. Example
The majority element is the element that appears more than  ⌊ n/2 ⌋  times
a= [1,1,1,3]   n=4 , 4/2 = 2
=> majority element 1 occur thrice

2. Implementation

Thought1: count element's occurences and loop to fins out whose occurences is larger than n/2
1-0 duplicate => hashSet or hashMap
1-1 a hashmap

Thought2: n/2 that means (n/2) / (n) = 1/2 with half probability to pick up the majority element
NOTE: count =0 reset last element
if curr = last element, count++
else count--

// NOTE: snippet

if (count == 0 ) { 

lastElem = nums[i]; 

count++; 

} else if ( lastElem == nums[i] ) { 

count++; 

} else {

 count--; 

}


<>

Time:O(2*n), Space:O(n) hashmap
public int majorityElement (int[] nums)
{
     // valid the input
     if ( nums == null || nums.length == 0)
     {
         return -1;
     }
  

     HashMap  map = new HashMap();
     for (int i = 0 ; i < nums.length;i++)
     {
          if (   map.containsKey(nums[i])  )
          {
                 map.put(nums[i], map.get(nums[i] + 1 );
          }
          else 
          {
                 map.put(nums[i], 1);
          }
     }
     


     //for (Entry e: map)
     for (Entry e: map.EntrySet() )
     {
          if (e.getValue() > (nums.length >>1) )
          {
              return e.getKey();
          }
     }

}

     for (int key: map.keySet())
     {
         if (map.get(key) > (nums.length >>1) )
         {
             return key;
         }
     }

Time:O(n), space:O(1)
public int majorityElement(int[] nums)
{
     // validate the input
     if ( nums == null || nums.length == 0 )
     {
        return -1;
     }


     int count = 0;
     int lastElem = nums[0];
     for (int i=1 ;i < nums.length;i++)
     {
        
         //if (lastElem == nums[i])
         //{ 
         //     count++;
         //}
         //else 
         //{
         //     count = 0;
         //     lastElem = num[i];
         //}

         if (count == 0 ) 
         {
              lastElem = nums[i];
              count++;
         }
         else if ( lastElem == nums[i] )
         {
              count++;
         }
         else 
         {
              count--;
         }
     }




     int count2 =0;
     for (int i = 0 ; i < nums.length;i++)
     {
         if ( lastElem == nums[i] )
         {
             count2++;
         }
     }
     if ( count2 > (nums.length>>1) )
     {
         return lastElem;
     }
     return -1;
}

3. Similar Ones
(M) Majority Element