public List<Integer> majorityElement(int[] nums) {
if (nums == null  nums.length == 0)
return new ArrayList<Integer>();
List<Integer> result = new ArrayList<Integer>();
int number1 = nums[0], number2 = nums[0], count1 = 0, count2 = 0, len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] == number1)
count1++;
else if (nums[i] == number2)
count2++;
else if (count1 == 0) {
number1 = nums[i];
count1 = 1;
} else if (count2 == 0) {
number2 = nums[i];
count2 = 1;
} else {
count1;
count2;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < len; i++) {
if (nums[i] == number1)
count1++;
else if (nums[i] == number2)
count2++;
}
if (count1 > len / 3)
result.add(number1);
if (count2 > len / 3)
result.add(number2);
return result;
}
JAVAEasy Version To Understand!!!!!!!!!!!!


@Reborn_ you can just use an array if it is a n/k question. it will be something like this...
public class Solution { public List<Integer> majorityElement(int[] nums) { int n = nums.length, k = 3; //in this question, k=3 specifically List<Integer> result = new ArrayList<Integer>(); if (n==0  k<2) return result; int[] candidates = new int[k1]; int[] counts = new int[k1]; for (int num: nums) { boolean settled = false; for (int i=0; i<k1; i++) { if (candidates[i]==num) { counts[i]++; settled = true; break; } } if (settled) continue; for (int i=0; i<k1; i++) { if (counts[i]==0) { counts[i] = 1; candidates[i] = num; settled = true; break; } } if (settled) continue; for (int i=0; i<k1; i++) counts[i] = (counts[i] > 0) ? (counts[i]1) : 0; } Arrays.fill(counts, 0); for (int num: nums) { for (int i=0;i<k1; i++) { if (candidates[i]==num) { counts[i]++; break; } } } for (int i=0; i<k1; i++) if (counts[i]>n/k) result.add(candidates[i]); return result; } }


@Oldman09 If you understand clearly about Major Element 1, this is definitely the easiest version to understand.

@Oldman09 since it requires more than n /3, so there should be no more than 2 elements. hope it helps


@DamaoServices This generalized solution is really nice for such n/k problems. Thanks!

@DamaoServices great solution, emulate your method:
class Solution { public List<Integer> majorityElement(int[] nums) { List<Integer> res = new ArrayList<>(); int k = 3; if(k<=1  nums.length<1){ return res; } int[] count = new int[k1]; int[] candidates = new int[k1]; Arrays.fill(count,0); Arrays.fill(candidates,nums[0]); for(int ele:nums){ boolean check = false; for(int i=0;i<k1;i++){ if(candidates[i] == ele){ count[i]++; check = true; break; } } if(check == true){ continue; } for(int i=0;i<k1;i++){ if(count[i]==0){ check = true; candidates[i] = ele; count[i] = 1; } } if(check == true){ continue; } for(int i=0;i<k1;i++){ count[i]; } } Set<Integer> set = new HashSet<>(); Arrays.fill(count,0); for(int ele : nums){ for(int i=0;i<k1;i++){ if(candidates[i]==ele){ count[i]++; } if(count[i]>nums.length/k){ set.add(candidates[i]); } } } return new ArrayList<Integer>(set); } }

@zhouyi_naive You have to check that the number is not equal to num_a and num_b first. Otherwise, even if it is equal to num_b and should be added to count_b, it might be added to num_a just because count_a is empty. So the 'if a== n' and 'elif b == n' checks have to be done together, at the beginning.
