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.
如果没有这时间空间要求,就跟 169 Majority Element 那题一样,用hash table, 或者 sort 都能很方便的实现。但是加上这些时间空间要求后,一开始想不出思路。
说明没有彻底理解169题中那种 O(n) 的方法。这题的解法和那种方法相似。
public class Solution { public List<Integer> majorityElement(int[] nums) { List<Integer> list = new ArrayList<>(); if (nums == null) return null; if (nums.length < 3) { for (int i = 0; i < nums.length; i++) { if (!list.contains(nums[i])) list.add(nums[i]); } return list; } int val1 = nums[0], val2 = nums[1], count1 = 0, count2 = 0; for (int i = 0; i < nums.length; i++) { if (val1 == nums[i]) count1++; else if (val2 == nums[i]) count2++; else if (count1 == 0) { val1 = nums[i]; count1++; } else if (count2 == 0) { val2 = nums[i]; count2++; } else { count1--; count2--; } } check(nums, val1, val2, list); return list; } public void check(int[] nums, int val1, int val2, List<Integer> list) { int count1 = 0, count2 = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == val1) count1++; else if (nums[i] == val2) count2++; } if (count1 > nums.length / 3) list.add(val1); if (count2 > nums.length / 3) list.add(val2); } }
2015-10-21