169. Majority Element

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

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:

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

Example 2:

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

Code

229. Majority Element II

Boyer-Moore Majority Vote Algorithm

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

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int res = 0;

        for(int num : nums){
            if(count == 0){
                res = num;
            }

            if(num != res){
                count--;
            } else {
                count++;
            }
        }

        return res;
    }
}