原题如下：

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:

思路如下：

原题是要找出现超过一半次数的元素。

学到一个特别巧妙地算法：Moore's voting algorithm

算法的详细解释在这个链接：http://www.bubuko.com/infodetail-589281.html

这个算法可以解决这样的问题：从一个数组中找出出现半数以上的元素。

算法的基本思想是，在数组中每次都找一组不相同的元素删掉，直到数组为空或只有一种元素。

不难证明，如果存在元素e出现频率超过半数，那么数组中最后剩下的就只有e。

当然如果遇到这种情况1.2.3结果是3显然错误，所以要重新扫一遍数组确定一下，时间复杂度是O（n）。

下面给出两个ac代码

代码如下：

（1）nlogn的算法

class Solution {

public:

int majorityElement(vector<int>& nums) {

int n = nums.size();

sort(nums.begin(),nums.end());

return nums[n/2];

}

};

（2）O(n)的算法

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;

}

　　};