Majority Element
Question
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Analysis
Boyer-Moore Majority
直接Array排序后找最多会超时
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
public class { public int majorityElement(int[] num) { int major=num[0], count = 1; for(int i=1; i<num.length;i++){ if(count==0){ count++; major=num[i]; }else if(major==num[i]){ count++; }else count--; } return major; } }
|
Majority Element II
Question
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.
Analysis
最多只可能有两个符合条件的元素,利用两个cnt和num记录
第一次遍历找到可能符合条件的num,再一次遍历确定是否超过n/3
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
|
public class { public List<Integer> majorityElement(int[] nums) { List<Integer> res=new ArrayList<>(); if(nums.length==0) return res; int cnt1=0; int cnt2=0; int num1=0; int num2=1; for(int i=0;i<nums.length;i++){ if(nums[i]==num1) cnt1++; else if(nums[i]==num2) cnt2++; else if(cnt1==0){ cnt1=1; num1=nums[i]; } else if(cnt2==0){ cnt2=1; num2=nums[i]; } else{ cnt1--; cnt2--; } } int count1=0; int count2=0; for(int i=0;i<nums.length;i++){ if(nums[i]==num1) count1++; else if(nums[i]==num2) count2++; } if(count1>nums.length/3) res.add(num1); if(count2>nums.length/3) res.add(num2); return res; } }
|
近期评论