229. Majority Element II 发表于 2022-09-12 Moore12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152class Solution { public List<Integer> majorityElement(int[] nums) { int candidate1 = 0; int candidate2 = 0; int votes1 = 0; int votes2 = 0; for (int num : nums) { // 注意需要先比较相等,都不相等的情况下再比较票数是否为 0, 如果先比较票数是否为 0, 则可能出现两个候选人使用同一个数字的情况 // eg: [2, 1, 1, 3, 1, 4, 5, 6] if (num == candidate1) { votes1++; } else { if (num == candidate2) { votes2++; } else { if (votes1 == 0) { candidate1 = num; votes1++; } else if (votes2 == 0) { candidate2 = num; votes2++; } else { votes1--; votes2--; } } } } int count1 = 0; int count2 = 0; for (int num : nums) { if (num == candidate1) { count1++; } else if (num == candidate2) { // 注意此处是 else if, 主要处理数组为 [0, 0] 这种情况,此时两个 candidate 值相同 count2++; } } List<Integer> list = new ArrayList<>(); if (count1 > nums.length / 3) { list.add(candidate1); } if (count2 > nums.length / 3) { list.add(candidate2); } return list; }} Moore1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253class Solution { public List<Integer> majorityElement(int[] nums) { int candidate1 = 0; int candidate2 = 0; int votes1 = 0; int votes2 = 0; for (int num : nums) { if (num == candidate1) { votes1++; continue; } if (num == candidate2) { votes2++; continue; } if (votes1 == 0) { candidate1 = num; votes1++; continue; } if (votes2 == 0) { candidate2 = num; votes2++; continue; } votes1--; votes2--; } int count1 = 0; int count2 = 0; for (int num : nums) { if (num == candidate1) { count1++; } else if (num == candidate2) { count2++; } } List<Integer> list = new ArrayList<>(); if (count1 > nums.length / 3) { list.add(candidate1); } if (count2 > nums.length / 3) { list.add(candidate2); } return list; }} Reference229. Majority Element II