Problem: Given an array consisting of N integers, find the number with the maximum occurrences, majority element, given the assumption that the number occurs more than N/2 times in the array.

Solution: Given the assumption that the element occurs more than N/2 times in the array simplifies the solution a lot. This is so because if more than N/2 elements are the same, it implies that all other elements combined are less than N/2. Hence, the difference between the count of majority element and the count of non-majority numbers will always be positive. This approach can significantly simplify our code to the problem.

In the solution we consider the first element as the majority element and keep the count as 1. Now we compare the second (next) element with this element. If it is the same element we increase the count to 2, else decrease the count to ZERO and keep the first element as the majority element. Check the next element. If it is equal increase the count, else set the majority element to be the given current element and make the count as ONE.

This way, at the end of the traversal of the list, we will have the majority element with us. As comparison between two elements takes constant time, the code will run in O(n) time where n is the number of elements in the list.

/**
 * Copyright (C) 2011, Sandeep Gupta
 * http://www.sangupta.com
 * 
 * The file is licensed under the the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * 
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * 
 */

public class MajorityElement {
 
 public static void main(String[] args) {
  int[] list = new int[] {1, 2, 3, 4, 2, 3, 4, 2, 3, 2, 1, 2, 3, 4, 2, 2, 2};
  
  int count = 1;
  int majorityElement = list[0];
  for(int index = 1; index < list.length; index++) {
   if(majorityElement != list[index]) {
    if(count == 0) {
     majorityElement = list[index];
     count++;
    } else {
     count--;
    }
   } else {
    count++;
   }
  }
  
  System.out.println("Majority Element: " + majorityElement);
 }

}

Hope this helps.

written by Sandeep Gupta

Monday, May 2, 2011 at 1:25 PM

Comments

0 responses to ' Majority Element in an Array '

Post Comments