Majority Element

Posted on Edited on In Word count in article: 210 Reading time ≈ 1 mins.

Introduction

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

A simple naive method is to sort array first and return the middle item, but the time complexity is O(N*log(N)). A better O(N) solution uses Moore Voting algorithm that keeps a temporary major element and update it while traversing the whole array. Use count to count the occurrence of same element by incrementing it and decrement it when encounter a different number, replace major element with current number when count = 0. As the number of majority element is larger than the rest of numbers, it won’t be cancelled out and stay at the end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class MajorityElement {
  // Method 1: Sorting
  public int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
  }

  // Method 2: Moore Voting algorithm that cancels out different items in list and majority element will stay at last.
  public int majorityElement2(int[] nums) {
    int count = 0, ret = 0;
    for(int i=0; i<nums.length; i++) {
      if(count == 0) ret = nums[i];
      if(nums[i] != ret) count--;
      else count++;
    }
    return ret;
  }
}