原题网址; https://www.lintcode.com/problem/majority-element-ii/
描述
给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的三分之一。
数组中只有唯一的主元素
您在真实的面试中是否遇到过这个题？ 是
样例
给出数组[1,2,1,2,1,3,3] 返回 1
挑战
要求时间复杂度为O(n)，空间复杂度为O(1)。
查看标签
枚举法
贪心
思路：利用map，建立nums【i】与数量count 的映射，最后返回 count 大于元素个数三分之一的nums【i】。
AC代码：
class Solution {
public:
/*
* @param nums: a list of integers
* @return: The majority number that occurs more than 1/3
*/
int majorityNumber(vector<int> &nums) {
// write your code here
int n=nums.size();
map<int,int> m;
for (int i=;i<n;i++)
{
m.insert(pair<int,int>(nums[i],));
}
for (int i=;i<n;i++)
{
m[nums[i]]++;
}
for (int i=;i<n;i++)
{
if (m[nums[i]]>n/)
{
return nums[i];
}
}
}
};另一种方法：摩尔投票法 可参照：摩尔投票法 https://blog.csdn.net/krystalhuang/article/details/71512901 以及 https://www.cnblogs.com/ZhangYushuang/p/4627503.html
思路：
1, 超过n/3的元素个数最多两个
2, 数组中连续3个数据为一组的话,一共n/3组,那么如果存在符合条件的元素,这个元素一定出现在某一个组内至少两次
3, 知道了以上两个条件后,用所谓的摩尔投票法,共两轮,
第一轮:找出出现次数最多的两个元素,每次存储两个元素n1和n2【注意n1 != n2】,如果第三个元素与其中一个相同,则增加计数cn1或cn2, 否则,清除n1和n2,从下一个数据开始重新统计.
根据第二条,数目较多的元素一定可以被查到,当然查到的不一定是大于n/3的.【有可能是连续3个为一组某个数字出现两~三次】
第二轮:验证这两个元素是否满足条件,即出现的次数是否大于n/3;
AC代码：
class Solution {
public:
/*
* @param nums: a list of integers
* @return: The majority number that occurs more than 1/3
*/
int majorityNumber(vector<int> &nums) {
// write your code here
int n=nums.size();
int candidate1,candidate2,count1=,count2=;
for (int i=;i<n;i++)
{
if (count1==)
{
candidate1=nums[i];
count1=;
}
else if (count2==&&nums[i]!=candidate1) //注意此处的nums[i]!=candidate1，两个candidate不能是同一个数;
{
candidate2=nums[i];
count2=;
}
else if (nums[i]==candidate1)
{
count1++;
}
else if (nums[i]==candidate2)
{
count2++;
}
else
{
count1--;
count2--;
}
}
count1=count2=;
for (int i=;i<n;i++)
{
if (nums[i]==candidate1)
{
count1++;
}
if (nums[i]==candidate2)
{
count2++;
}
}
if (count1>n/)
{
return candidate1;
}
if (count2>n/)
{
return candidate2;
}
}
};该代码在lintcode网站上可以通过，但是放在VS2010下运行出错，原因是 candidate1 与 candidate2 未初始化，想不明白原因啊，费解。