[LeetCode] 169. Majority Element

Posted on | In

Problem

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.

Example 1:

1
2
Input: [3,2,3]
Output: 3

Example 2:

1
2
Input: [2,2,1,1,1,2,2]
Output: 2

Explanation

  1. Using Moore Voting algorithm, initialize the first number be the result, count is 1. When we hit the second number, if the second number is equal to the first number, then we just increase count by 1. Else if the second number is not the same, then we decreae the count by 1. When we hit the next number, if the count is 0, then we update result to be that number and increase count by 1.

  2. This method only works when the majority element has more than half number of the elements.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int majorityElement(int[] nums) {
        int res = nums[0], cnt = 0;
        for (int num: nums) {
            if (cnt == 0) {
                res = num;
                cnt = 1;
            } else if (num == res) {
                cnt += 1;
            } else {
                cnt -= 1;
            }
        }

        return res;
    }
}