229. Majority Element II

229. Majority Element II

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.

class Solution { public List majorityElement(int[] nums) { int num1 = 0, num2 = 1; int count1 = 0, count2 = 0; for(int num: nums) { if (count1 == 0) { num1 = num; count1 = 1; } else if (num1 == num) { count1 ++; } else if (count2 == 0) { num2 = num; count2 = 1; } else if (num2 == num) { count2 ++; } else { count1 --; count2 --; if (count1 == 0 && count2 > 0) { num1 = num2; count1 = count2; num2 = 0; count2 = 0; } } } if (count1 > 0) { count1 = 0; for(int num: nums) if (num1 == num) count1 ++; } if (count2 > 0) { count2 = 0; for(int num: nums) if (num2 == num) count2 ++; } List results = new ArrayList<>(); if (count1*3>nums.length) results.add(num1); if (count2*3>nums.length) results.add(num2); return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。