⌊ n/3 ⌋
times. The algorithm should run in linear time and in O(1) space.Solution 1: possible at most 2 candidates num1 and num2, so when iterate the array, num1 and num2 must appear more then n/3 times. Other nums not num1/2 appear less then n/3 times.
public class Solution {
public List<Integer> majorityElement(int[] nums) {
int num1=0, num2=0, c1=0, c2=0;
for (int x:nums) {
if (c1>0 && x==num1) c1++;
else if (c2>0 && x==num2) c2++;
else if (c1==0) {
num1=x;
c1++;
}
else if (c2==0) {
num2=x;
c2++;
}
else {
c1--;
c2--;
}
}
c1=0;c2=0;
for (int x:nums) {
if (x==num1) c1++;
else if (x==num2) c2++;
}
List<Integer> res=new ArrayList<>();
if (c1>nums.length/3) res.add(num1);
if (c2>nums.length/3) res.add(num2);
return res;
}
}
没有评论:
发表评论