[LeetCode] Majority Element II
Majority Element II
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.
解题思路:
此前做了一道题目,返回主要元素,其中主要元素的定义是出现次数大于n/2的元素。当初投票法非常不错。类似的,这道题也可以用投票法,但是稍微复杂一下。注意到,对于一个数组来说,大于n/3的元素最多有2个。于是可以用两个变量来记录出现的候选主要元素。
设候选主要元素为can1,can2,其票数分别是count1,count2(初始化均为0)。逐个扫描nums内的元素nums[i],分情况讨论。
1、假设还未统计任何数,即count1=0&&count2=0,则can1=nums[i],count1=1
2、can1和can2其中一个没有初始化(设can2,即count2=0),且nums[i]!=can1,那么can2=nums[i],count2=1。对称另一种情况容易知道。
3、假设can1和can2两个都初始化了(count1!=0并且count2!=0),但是can1!=nums[i]并且can2!=nums[i]。那么count1和count2均减1
4、若count1!=0并且can1==nums[i],那么count1++。同样,若count2!=0并且can2==nums[i],那么count2++。
最后,验证can1和can2的出现次数即可。
下面是代码:
class Solution { public: vector<int> majorityElement(vector<int>& nums) { vector<int> result; int len = nums.size(); int can1=0, count1 = 0, can2 = 0, count2 = 0; for(int i=0; i<len; i++){ if(count1 == 0 && count2 == 0){ can1 = nums[i]; count1=1; }else if(count1!=0 && count2!=0 && can1!=nums[i] && can2!=nums[i]){ count1--; count2--; }else if(can1==nums[i] && count1!=0){ count1++; }else if(can2==nums[i] && count2!=0){ count2++; }else if(count1==0&&count2!=0&&can2!=nums[i]){ can1 = nums[i]; count1++; }else if(count2==0&&count1!=0&&can1!=nums[i]){ can2 = nums[i]; count2++; } } //这两个只是候选的 if(count1!=0){ count1 = 0; for(int i=0; i<len; i++){ if(can1==nums[i]){ count1++; } } if(count1>len/3){ result.push_back(can1); } } if(count2!=0){ count2 = 0; for(int i=0; i<len; i++){ if(can2==nums[i]){ count2++; } } if(count2>len/3){ result.push_back(can2); } } return result; } };
0 条评论