Majority Element (Easy)

Description

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.

Analysis

找出一个整数，它的个数是整个数组的1/2以上。那么我们想象一下，其他数字与它一一对应的话
肯定有剩余存在，而这个剩余的数字就是那个要找的。所以，我们记录每次一一对应的数字，不同则抵消

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//C++
class Solution {
public:
    int majorityElement(vector<int> &num) {
        int ans,same=0;
        for(int i=num.size()-1;i>=0;i--){
            if(same == 0){
                ans = num[i];
                same++;
            }
            else{
                if(num[i]==ans)
                    same++;
                else
                    same--;
            }
        }
        return ans;
    }
};