LeetCode Daily Question 22

5 月 6 日 每日一题

题目：169. Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

1
2
3
4

Example 1:

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

思路

本题使用 Boyer–Moore majority vote algorithm，因为条件是必然存在 majority，本质可以理解为为每一个元素寻找一个不同的元素进行配对，应该存在 n/2 个 pair，但 majority 一定出现多于 n/2 次，所以最终剩余的无法配对的元素就是 majority。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int majority = nums[0];
        for(auto &num: nums){
            if(count >= 1)
                count += (num == majority) ? 1 : -1;
            else{
                majority = num;
                count = 1;
            }
        }
        return majority;
    }
};