Java program to find majority element in an unsorted array

In this article, we will learn how to find majority element in an unsorted array in Java.

This is a frequently asked interview question.

The majority element is the element that appears more than [ n/2 ] times.

 
Here are few approaches to find the majority element :

 

Find majority element in an unsorted array using HashMap

package temp;

import java.util.HashMap;
import java.util.Map;

public class MajorityElementAlgorithm {

  public static void main(String[] args) {
    int[] arr = { 1, 2, 3, 4, 5, 2, 2, 2, 2 };
    try {
      int majorityElement = findMajorityElement(arr);
      System.out.println("Majority element in the array is "
          + majorityElement);
    } catch (Exception e) {
      e.printStackTrace();
    }
  }

  private static int findMajorityElement(int[] x) throws Exception {
    Map<Integer, Integer> d = new HashMap<Integer, Integer>();
    int majority = x.length / 2;

    // Stores the number of occurrences of each item in the passed array in
    // a map
    for (int i : x)
      if (d.containsKey(i)) {
        int value = d.get(i);
        value++;
        d.put(i, value);
        // Checks if element just added is the majority element
        if (value > majority)
          return i;
      } else
        d.put(i, 1);
    // No majority element
    throw new Exception("No majority element in array");
  }

}

Output :

Majority element in the array is 2
 

Find majority element in an unsorted array with nested loops

  private static int findMajorityElement_2(int[] a) throws Exception {
    int tempCount;
    int majority = a[0];
    int temp = 0;
    int majorityCount = a.length / 2;
    for (int i = 0; i < (a.length - 1); i++) {
      temp = a[i];
      tempCount = 0;
      for (int j = 1; j < a.length; j++) {
        if (temp == a[j])
          tempCount++;
      }
      if (tempCount > majorityCount) {
        majority = temp;
        return majority;
      }
    }
    // No majority element
    throw new Exception("No majority element in array");
  }

Output :

Majority element in the array is 2
 

Find majority element using sorting

  private static int findMajorityElement_3(int[] x){
    if (x.length == 1) {
      return x[0];
    }
   
    Arrays.sort(x);
    return x[x.length / 2];
  }

Output :

Majority element in the array is 2
 

Find majority element in an unsorted array using Linear Time Majority Vote Algorithm

Reference : http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

  private static int findMajorityElement_4(int[] x) {
    int majority = 0, count = 0;
    for (int i = 0; i < x.length; i++) {
      // If count is 0, set the current candidate to majority and set count to 1
      if (count == 0) {
        majority = x[i];
        count = 1;
      }
      //increase counter if majority is the element at i
      else if (x[i] == majority) {
        count++;
      } 
      // decrease count
      else {
        count--;
      }
    }
    return majority;
  }

Output :

Majority element in the array is 2
 

© 2017, https:. All rights reserved. On republishing this post, you must provide link to original post

One comment

  1. […] Given an unsorted array which has a number in the majority (a number appears more than 50% in the array), find that number?(Solution) […]

Leave a Reply.. code can be added in <code> </code> tags

%d bloggers like this: