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.
思路:
找到一个数组中出现次数超过一半的数。排序、哈希等方法就不提了,考虑O(n)的复杂度,有一种传说中的摩尔投票算法可用。其实也很简单,初始选第一个元素,依次比对它和其它的元素,若相等则其票数加一,反之则减一,当其票数为0时,更换投票对象为当前的元素,继续执行,最终即可得结果(前提的数组中存在这样的数,否则结果不确定是什么,依赖于元素的摆放顺序)。
C++:
class Solution {
public:
int majorityElement(vector<int> &num) { int len = num.size();
if(len == )
return ; int cnt = , ret = num[];
for(int i = ; i < len; i++)
{
if(cnt == )
{
ret = num[i];
cnt++;
}
else
{
if(num[i] == ret)
cnt++;
else
cnt--;
}
}
return ret;
}
};
Python:
class Solution:
# @param {integer[]} nums
# @return {integer}
def majorityElement(self, nums):
ret, cnt = 0, 0 for val in nums:
if cnt == 0:
ret = val
cnt = 1
else:
if ret == val:
cnt = cnt + 1
else:
cnt = cnt - 1
return ret