dustfree's blog
0%

Majority Element

Posted on In ,

Question

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:
Input: [3,2,3]
Output: 3

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
Algorithm: 某一元素次数大于一半，将数组里看成两种元素，一种是res，另一种是非res。
记录一个count和对应的num，如果后面元素相等，则count++,反之--，最后count >= 1则num记为res
*/
public int majorityElement(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    
    int count = 0, curMajority = 0;        
    for (int num : nums) {
        if (count == 0) {
            curMajority = num;
        }
        
        if (num == curMajority) {
            count++;
        }else {
            count--;
        }
    }
    return curMajority;
}