[LeetCode 229] Majority element II

CSDN专家精选，微信开发学习路线大有看头！【博乐】点评美文，得C币【脑洞趴】iOS开发前沿与Swift探秘Swift教程大汇总

[LeetCode 229] Majority element II

分类：LeetcodeJava

leetcode

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.

Solution:

At most has two elements in the result, can use two counter to record occurrence. Then calculate if match the condition.

public List<Integer> majorityElement(int[] nums) {List<Integer> result = new ArrayList<>();if(nums.length==0) return result;int n1 = nums[0];int n2 = 0;int count1 = 1;int count2 = 0;for(int i=1;i<nums.length;i++){if(nums[i] == n1){count1++;}else if(nums[i] == n2){count2++;}else{if(count1 == 0){n1 = nums[i];count1++;}else if(count2 == 0){n2 = nums[i];count2++;}else{count1–;count2–;}}}count1 = 0;count2 = 0;for(int i=0;i<nums.length;i++){if(nums[i] == n1) count1++;if(nums[i] == n2) count2++;}if(count1>nums.length/3) result.add(n1);if(n1 == n2) return result;if(count2>nums.length/3) result.add(n2);return result;}

版权声明：本文为博主原创文章，，未经博主允许不得转载。

上一篇erasure coding下一篇[Leetcode172]Factorial Trailing Zeroes

猜你在找

查看评论

* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场

如果可以，我真想和你一直旅行。