Majority Element

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.

thinking:

令A[1..n]是一个整数序列，A中的整数a如果在A中出现的次数多于 ⌊ n/2 ⌋ ，那么a称为多数元素。例如，在序列2,2,2,8,2,4,3,2中，2是多数元素，因为8个元素中它出现5次。当然多数元素要么不存在，要么就只有一个。 每找出两个不同的element，就成对删除即count- -，最终剩下的一定就是所求的。时间复杂度：O(n)。

solution：

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