[LeetCode] Majority Element

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Hide Tags

 Divide and Conquer Array Bit Manipulation

 

---

　　这题是简单的一道遍历问题。

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int> &num) {
        int n = num.size();
        int cnt = 1;
        int nowInt = num[0];
        for(int i =1;i<n;i++){
            if(num[i]==nowInt){
                cnt++;
                continue;
            }
            cnt--;
            if(cnt<0){
                cnt = 1;
                nowInt = num[i];
            }
        }
        return nowInt;
    }
};

int main()
{
    vector<int> num ={1,2,4,4,1,2,2,3,1,1,1,1,1,1,1,1};
    Solution sol;
    cout<<sol.majorityElement(num)<<endl;
    return 0;
}