本文共 3463 字,大约阅读时间需要 11 分钟。
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
Hint:
How many majority elements could it possibly have?
Do you have a better hint? Suggest it!给一个大小为n的数组,找出所有的出现次数超过n/3的元素。
算法要求是线性时间,即O(N),O(1)的空间复杂度。这一题印象深刻!!!因为它的解法太巧妙了,每次想起都会赞叹不已!
解决方法:摩尔投票法!!!
思想就是寻找这个数组中出现次数最多的两个元素(只有两个有可能是大于n/3)。 然后看这两个元素的出现次数是否超过n/3,超过就加入结果中,否则,舍弃。 那么如何求出现次数最多的两个元素呢? 看代码,很简单:int m=0,n=1,count_m=0,count_n=0;for(auto elem:nums)//相当于nums[i]。这一步很重要,也很巧妙!是寻找数组中最多的两个元素。{ if(elem==m) count_m++; else if(elem==n) count_n++; else if(!count_m) m=elem,count_m=1; else if(!count_n) n=elem,count_n=1; else count_m--,count_n--;}
然后重新遍历,再次计数
count_m=0,count_n=0;for(auto elem:nums){ if(elem==m) count_m++; else if(elem==n) count_n++;}if(count_m>size_n/3) res.push_back(m);if(count_n>size_n/3) res.push_back(n);
AC代码:
class Solution { //摩尔投票法,n=3的情形public: vector majorityElement(vector & nums) { vector res; int size_n=nums.size(); //if(size_n==0) return res;//这一步其实也不需要 /*if(size_n==1) //经过验证,其实不需要这一个判断 { res.push_back(nums[0]); return res; }*/ //处理个数大于等于2的情形 int m=0,n=1,count_m=0,count_n=0; for(auto elem:nums)//相当于nums[i]。这一步很重要,也很巧妙!是寻找数组中最多的两个元素。 { if(elem==m) count_m++; else if(elem==n) count_n++; else if(!count_m) m=elem,count_m=1; else if(!count_n) n=elem,count_n=1; else count_m--,count_n--; } count_m=0,count_n=0; for(auto elem:nums) { if(elem==m) count_m++; else if(elem==n) count_n++; } if(count_m>size_n/3) res.push_back(m); if(count_n>size_n/3) res.push_back(n); return res; }};
当n=4,5,6…k时,方法也是如此
比如n=5 代码未经过验证class Solution1 { //摩尔投票法,n=5的情形public: vector majorityElement(vector & nums) { vector res; int size_n = nums.size(); //if(size_n==0) return res;//这一步其实也不需要 /*if(size_n==1) //经过验证,其实不需要这一个判断 { res.push_back(nums[0]); return res; }*/ //处理个数大于等于5的情形 //暂时不对异常进行处理 int m = 0, n = 1, count_m = 0, count_n = 0; int Data[5] = { 0 }; int DataNum[5] = { 0 }; for (auto elem : nums)//相当于nums[i]。这一步很重要,也很巧妙!是寻找数组中最多的两个元素。 { bool flag = 1; for (int j = 0; j < 5; j++) { if (elem == Data[j]) { DataNum[j]++; flag = 0; break; } } for (int j = 0; flag&&j < 5; j++) { if (!DataNum[j]) { Data[j] = elem; DataNum[j]=1; flag = 0; break; } } for (int j = 0; flag&&j < 5; j++) { Data[j]--; } } for (int j = 0;j < 5; j++) { DataNum[j]=0; } for (auto elem : nums) { for (int j = 0; j < 5; j++) { if (elem == Data[j]) { DataNum[j]++; } } } if (count_m>size_n / 5) res.push_back(m); if (count_n>size_n / 5) res.push_back(n); return res; }};
转载地址:http://xexvi.baihongyu.com/