Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Note
The algorithm should run in linear time and in O(1) space.
Example
No.1
Input: [3,2,3]
Output: [3]
No.2
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
|
public List<Integer> (int[] nums) { List<Integer> result = new ArrayList<>(); int candidate1 = 0; int candidate2 = 0; int count1 = 0; int count2 = 0;
for (int num : nums) { if (num == candidate1) count1++; else if (num == candidate2) count2++; else if (count1 == 0) { count1 = 1; candidate1 = num; } else if (count2 == 0) { count2 = 1; candidate2 = num; } else { count1--; count2--; } }
count1 = 0; count2 = 0;
for (int num : nums) { if (num == candidate1) count1++; else if (num == candidate2) count2++; }
if (count1 > nums.length / 3) result.add(candidate1); if (count2 > nums.length / 3) result.add(candidate2);
return result; }
|
近期评论