Related: LeetCode 169+ LintCode: Majority Number I
Lintcode: Majority Number II - neverlandly - 博客园
Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array. Find it.
Note There is only one majority number in the array Example For [1, 2, 1, 2, 1, 3, 3] return 1
X.
https://leetcode.com/problems/majority-element-ii/discuss/174987/topic
https://discuss.leetcode.com/topic/29390/concise-java-solution-based-on-moore-s-voting-algorithm
http://blog.csdn.net/nicaishibiantai/article/details/43635069
What if the frequency becomes 5/n or 6/n or...? Then do we need to define 5 or 6 counts?
https://reeestart.wordpress.com/2016/07/01/google-majority-number-sorted/
Lintcode: Majority Number II - neverlandly - 博客园
Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array. Find it.
Note There is only one majority number in the array Example For [1, 2, 1, 2, 1, 3, 3] return 1
X.
https://leetcode.com/problems/majority-element-ii/discuss/174987/topic
思路：摩尔投票升级版，超过n/3的数最多只能有两个；
先选出两个候选人A,B,遍历数组，如果投A（等于A），则A的票数++;如果投B，B的票数++；
如果A,B都不投（即与A，B都不相等）,那么检查此时是否AB中候选人的票数是否为0，如果为0,则成为新的候选人；
如果A,B两个人的票数都不为0，那么A,B两个候选人的票数均--；
遍历结束后选出两个候选人，但是这两个候选人是否满足>n/3，还需要再遍历一遍数组，找出两个候选人的具体票数
*/
public List<Integer> majorityElement(int[] nums) {
if (nums==null||nums.length==0){
return null;
}
//初始化，定义两个候选人以及对应的票数
int candidateA=nums[0];
int candidateB=nums[0];
int countA=0;
int countB=0;
// 遍历数组
for (int num:nums){
if (num==candidateA){ //投A
countA++;
continue;
}
if (num==candidateB){// 投B
countB++;
continue;
}
//此时A,B都不投,检查是否有票数为0情况，如果为0，则更新候选人
if (countA==0){
candidateA=num;
countA++;
continue;
}
if (countB==0){
candidateB=num;
countB++;
continue;
}
//此时两个候选人的票数都大于1，且当前选名不投AB，那么A,B对应的票数都要--;
countA--;
countB--;
}
// 上一轮遍历找出了两个候选人，但是这两个候选人是否均满足票数大于N/3仍然没法确定，需要重新遍历，确定票数
countA=0;
countB=0;
for (int num:nums){
if (num==candidateA){
countA++;
}else if (num==candidateB){
countB++;
}
}
List<Integer> resultList=new ArrayList<>();
if (countA>nums.length/3){
resultList.add(candidateA);
}
if (countB>nums.length/3){
resultList.add(candidateB);
}
return resultList;
}
I found a great article (http://goo.gl/64Nams) that helps me to understand this fantastic algorithm!!
Please check it out!
Please check it out!
The essential concepts is you keep a counter for the majority number X. If you find a number Y that is not X, the current counter should deduce 1. The reason is that if there is 5 X and 4 Y, there would be one (5-4) more X than Y. This could be explained as "4 X being paired out by 4 Y".
And since the requirement is finding the majority for more than ceiling of [n/3], the answer would be less than or equal to two numbers.
So we can modify the algorithm to maintain two counters for two majorities.
So we can modify the algorithm to maintain two counters for two majorities.
Followings are my sample Python code:
class Solution:
# @param {integer[]} nums
# @return {integer[]}
def majorityElement(self, nums):
if not nums:
return []
count1, count2, candidate1, candidate2 = 0, 0, 0, 1
for n in nums:
if n == candidate1:
count1 += 1
elif n == candidate2:
count2 += 1
elif count1 == 0:
candidate1, count1 = n, 1
elif count2 == 0:
candidate2, count2 = n, 1
else:
count1, count2 = count1 - 1, count2 - 1
return [n for n in (candidate1, candidate2)
if nums.count(n) > len(nums) // 3]https://discuss.leetcode.com/topic/29390/concise-java-solution-based-on-moore-s-voting-algorithm
public List<Integer> majorityElement(int[] nums) {
if (nums == null || nums.length == 0)
return new ArrayList<Integer>();
List<Integer> result = new ArrayList<Integer>();
int number1 = nums[0], number2 = nums[0], count1 = 0, count2 = 0, len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] == number1)
count1++;
else if (nums[i] == number2)
count2++;
else if (count1 == 0) {
number1 = nums[i];
count1 = 1;
} else if (count2 == 0) {
number2 = nums[i];
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < len; i++) {
if (nums[i] == number1)
count1++;
else if (nums[i] == number2)
count2++;
}
if (count1 > len / 3)
result.add(number1);
if (count2 > len / 3)
result.add(number2);
return result;
}public List<Integer> majorityElement(int[] nums) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (nums.length==0) return res;
int count[] = new int[2];
int x[] = new int[2];
x[0] = 0; x[1] = 1;
for (int i = 0; i < nums.length; i++) {
if (x[0] == nums[i])
count[0]++;
else if (x[1] == nums[i])
count[1]++;
else if (count[0] == 0) {
x[0] = nums[i];
count[0] = 1;
} else if (count[1] == 0) {
x[1] = nums[i];
count[1] = 1;
} else {
count[0]--;
count[1]--;
}
}
Arrays.fill(count, 0);
for (int i : nums) {// Count again for x1, x2
if (i == x[0]) count[0]++;
else if (i == x[1]) count[1]++;
}
for (int j = 0; j < 2; j++) {
if (count[j] > nums.length/3 && !res.contains(x[j])) res.add(x[j]);
}
return res;
} public List<Integer> majorityElement(int[] nums) {
if (nums == null || nums.length == 0)
return new ArrayList<Integer>();
List<Integer> result = new ArrayList<Integer>();
int number1 = nums[0], number2 = nums[0], count1 = 0, count2 = 0, len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] == number1)
count1++;
else if (nums[i] == number2)
count2++;
else if (count1 == 0) {
number1 = nums[i];
count1 = 1;
} else if (count2 == 0) {
number2 = nums[i];
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < len; i++) {
if (nums[i] == number1)
count1++;
else if (nums[i] == number2)
count2++;
}
if (count1 > len / 3)
result.add(number1);
if (count2 > len / 3)
result.add(number2);
return result;
}http://blog.csdn.net/nicaishibiantai/article/details/43635069
1. 我们对cnt1,cnt2减数时，相当于丢弃了3个数字（当前数字，n1, n2）。也就是说，每一次丢弃数字，我们是丢弃3个不同的数字。
而Majority number超过了1/3所以它最后一定会留下来。
设定总数为N, majority number次数为m。丢弃的次数是x。则majority 被扔的次数是x
而m > N/3, N - 3x > 0.
3m > N, N > 3x 所以 3m > 3x, m > x 也就是说 m一定没有被扔完
最坏的情况，Majority number每次都被扔掉了，但它一定会在n1,n2中。
2. 为什么最后要再检查2个数字呢？因为数字的编排可以让majority 数被过度消耗，使其计数反而小于n2，或者等于n2.前面举的例子即是。
另一个例子：
1 1 1 1 2 3 2 3 4 4 4 这个 1就会被消耗过多，最后余下的反而比4少。
首先处理
count == 0的情况，这里需要注意的是count2 == 0 && key1 = num, 不重不漏。最后再次遍历原数组也必不可少，因为由于添加顺序的区别，count1 和 count2的大小只具有相对意义，还需要最后再次比较其真实计数器值。 public int majorityNumber(ArrayList<Integer> nums) {
if (nums == null || nums.isEmpty()) return -1;
// pair
int key1 = -1, key2 = -1;
int count1 = 0, count2 = 0;
for (int num : nums) {
if (count1 == 0) {
key1 = num;
count1 = 1;
continue;
} else if (count2 == 0 && key1 != num) {
key2 = num;
count2 = 1;
continue;
}
if (key1 == num) {
count1++;
} else if (key2 == num) {
count2++;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int num : nums) {
if (key1 == num) {
count1++;
} else if (key2 == num) {
count2++;
}
}
return count1 > count2 ? key1 : key2;
}
}public int majorityNumber(ArrayList<Integer> nums) { int candidate1 = 0, candidate2 = 0; int count1, count2; count1 = count2 = 0; for (int i = 0; i < nums.size(); i++) { if (candidate1 == nums.get(i)) { count1 ++; } else if (candidate2 == nums.get(i)) { count2 ++; } else if (count1 == 0) { candidate1 = nums.get(i); count1 = 1; } else if (count2 == 0) { candidate2 = nums.get(i); count2 = 1; } else { count1--; count2--; } } count1 = count2 = 0; for (int i = 0; i < nums.size(); i++) { if (nums.get(i) == candidate1) { count1++; } else if (nums.get(i) == candidate2) { count2++; } } return count1 > count2 ? candidate1 : candidate2; } }
这道题和LintCode的Majority Number II很像，但是稍有不同，需要考虑一个特殊情况：
When there are two different elements in the array, both of the two elements appear more than n/3 times.
Input:
[1,2]
Expected:
[1,2]
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return result;
}
int candidate1 = 0;
int candidate2 = 0;
int count1 = 0;
int count2 = 0;
for (int i = 0; i < nums.length; i++) {
if (count1 == 0) {
candidate1 = nums[i];
} else if (count2 == 0) {
candidate2 = nums[i];
}
if (nums[i] == candidate1) {
count1++;
}
else if (nums[i] == candidate2) {
count2++;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == candidate1) {
count1++;
}else if (nums[i] == candidate2) {
count2++;
}
}
if (count1 > nums.length / 3) {
result.add(candidate1);
}
if (count2 > nums.length / 3) {
result.add(candidate2);
}
return result;
}public List<Integer> majorityElement(int[] nums) { List<Integer> result = new ArrayList<Integer>(); Integer n1=null, n2=null; int c1=0, c2=0; for(int i: nums){ if(n1!=null && i==n1.intValue()){ c1++; }else if(n2!=null && i==n2.intValue()){ c2++; }else if(c1==0){ c1=1; n1=i; }else if(c2==0){ c2=1; n2=i; }else{ c1--; c2--; } } c1=c2=0; for(int i: nums){ if(i==n1.intValue()){ c1++; }else if(i==n2.intValue()){ c2++; } } if(c1>nums.length/3) result.add(n1); if(c2>nums.length/3) result.add(n2); return result; } |
Using Counter Map:
public List<Integer> majorityElement(int[] nums) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int i: nums){ if(map.containsKey(i)){ map.put(i, map.get(i)+1); }else{ map.put(i, 1); } } List<Integer> result = new ArrayList<Integer>(); for(Map.Entry<Integer, Integer> entry: map.entrySet()){ if(entry.getValue() > nums.length/3){ result.add(entry.getKey()); } } return result; } |
public int majorityNumber(ArrayList<Integer> nums) { 7 // write your code 8 // When there are only 1 or 2 elements in the array, 9 // there is no solution. 10 if (nums == null || nums.size() <= 2) { 11 return -1; 12 } 13 14 int n1 = 0; 15 int n2 = 0; 16 17 int cnt1 = 0; 18 int cnt2 = 0; 19 20 int size = nums.size(); 21 for (int i = 0; i < size; i++) { 22 int num = nums.get(i); 23 if (cnt1 != 0 && num == n1) { 24 cnt1++; 25 } else if (cnt2 != 0 && num == n2) { 26 cnt2++; 27 } else if (cnt1 == 0) { 28 cnt1 = 1; 29 n1 = num; 30 } else if (cnt2 == 0) { 31 cnt2 = 1; 32 n2 = num; 33 } else { 34 cnt1--; 35 cnt2--; 36 } 37 } 38 39 // count the two candiates. 40 cnt1 = 0; 41 cnt2 = 0; 42 for (int num: nums) { 43 if (num == n1) { 44 cnt1++; 45 } else if (num == n2) { 46 cnt2++; 47 } 48 } 49 50 if (cnt1 < cnt2) { 51 return n2; 52 } 53 54 return n1; 55 }X. Follow up: Generalization
What if the frequency becomes 5/n or 6/n or...? Then do we need to define 5 or 6 counts?
public List<Integer> majorityElement(int[] nums) {
int n = nums.length, k = 3; //in this question, k=3 specifically
List<Integer> result = new ArrayList<Integer>();
if (n==0 || k<2) return result;
int[] candidates = new int[k-1];
int[] counts = new int[k-1];
for (int num: nums) {
boolean settled = false;
for (int i=0; i<k-1; i++) {
if (candidates[i]==num) {
counts[i]++;
settled = true;
break;
}
}
if (settled) continue;
for (int i=0; i<k-1; i++) {
if (counts[i]==0) {
counts[i] = 1;
candidates[i] = num;
settled = true;
break;
}
}
if (settled) continue;
for (int i=0; i<k-1; i++) counts[i] = (counts[i] > 0) ? (counts[i]-1) : 0;
}
Arrays.fill(counts, 0);
for (int num: nums) {
for (int i=0;i<k-1; i++) {
if (candidates[i]==num) {
counts[i]++;
break;
}
}
}
for (int i=0; i<k-1; i++) if (counts[i]>n/k) result.add(candidates[i]);
return result;
} public List<Integer> majorityElement(int[] nums) {
if(nums == null || nums.length == 0) return new ArrayList<>();
return helper(nums, 3);
}
public List<Integer> helper(int[] nums, int k){
Map<Integer, Integer> majorities = new HashMap<>();
List<Integer> ret = new ArrayList<>();
for(int num : nums){
if(majorities.containsKey(num)) majorities.put(num, majorities.get(num) + 1);
else if(majorities.keySet().size() < k - 1) majorities.put(num, 1);
else{
Iterator<Map.Entry<Integer, Integer>> ite = majorities.entrySet().iterator();
while(ite.hasNext()){
Map.Entry<Integer, Integer> entry = ite.next();
int val = entry.getValue();
if(val == 1) ite.remove();
else entry.setValue(val - 1);
}
}
}
for(Integer i : majorities.keySet()){
majorities.put(i, 0);
}
for(int num : nums){
if(majorities.containsKey(num)) majorities.put(num, majorities.get(num) + 1);
}
int target = nums.length / k;
for(Integer i : majorities.keySet()){
if(majorities.get(i) > target) ret.add(i);
}
return ret;
}
I keep up to two candidates in my counter, so this fulfills the O(N) time and O(1) space requirements.
def majorityElement(self, nums):
ctr = collections.Counter()
for n in nums:
ctr[n] += 1
if len(ctr) == 3:
ctr -= collections.Counter(set(ctr))
return [n for n in ctr if nums.count(n) > len(nums)/3]
Explanation
Think of it this way: Find three different votes and hide them. Repeat until there aren't three different votes left. A number that originally had more than one third of the votes now still has at least one vote, because to hide all of its votes you would've had to hide more than three times one third of the votes - more votes than there were. You can easily have false positives, though, so in the end check whether the remaining up to two candidates actually had more than one third of the votes.
My code does just that: Collect (count) the votes for every number, but remove triples of three different votes on the fly, as soon as we have such a triple.
Generalization to ⌊N/k⌋, still O(N) time but O(k) space
For the general problem, looking for elements appearing more than ⌊N/k⌋ times for some positive integer k, I just have to change my
3 to k. Then it already works and takes takes O(k) space and O(kN) time.
The O(kN) time does not come from the main loop, though. Yes, each
ctr -= ... does cost k, but I only have to do it at most N/k times. To put it in terms of the above explanation, I can't hide a vote more than once.
No, the culprit is my last line, counting each remaining candidate separately. If I count them at the same time, I get O(N) again. Here's the full generalized code:
def majorityElement(self, nums, k):
ctr = collections.Counter()
for n in nums:
ctr[n] += 1
if len(ctr) == k:
ctr -= collections.Counter(set(ctr))
ctr = collections.Counter(n for n in nums if n in ctr)
return [n for n in ctr if ctr[n] > len(nums)/k]https://reeestart.wordpress.com/2016/07/01/google-majority-number-sorted/
给一个sorted array, 找出所有出现次数大于n/4的数。
[Solution]
看到sorted，应该很本能的反应出binary search。 但是这道题怎么binary search还是有点技巧。首先找出1/4, 2/4, 3/4三个数作为candidates, 因为题目要求是__大于n/4的才是majority，如果是大于等于__，那么就应该取1/4, 2/4, 3/4, 4/4四个candidates。
看到sorted，应该很本能的反应出binary search。 但是这道题怎么binary search还是有点技巧。首先找出1/4, 2/4, 3/4三个数作为candidates, 因为题目要求是__大于n/4的才是majority，如果是大于等于__，那么就应该取1/4, 2/4, 3/4, 4/4四个candidates。
取完candidates，对每个进行binary search分别找floor和ceiling，然后看index range是不是满足要求(大于n/4)。
[Note]
candidates之间注意去重，有可能某一个candidate甚至出现了超过n/2次。
candidates之间注意去重，有可能某一个candidate甚至出现了超过n/2次。
public List<Integer> majorityNumber(int[] nums) { List<Integer> result = new ArrayList<>(); if (nums == null || nums.length == 0) { return result; } int n = nums.length; int candidate1 = nums[n / 4]; int candidate2 = nums[n / 2]; int candidate3 = nums[3 * n / 4]; if (isMajority(nums, candidate1)) { result.add(candidate1); } if (candidate2 != candidate1 && isMajority(nums, candidate2)) { result.add(candidate2); } if (candidate3 != candidate2 && isMajority(nums, candidate3)) { result.add(candidate3); } return result; } private boolean isMajority(int[] nums, int candidate) { int floor = findFloor(nums, candidate); int ceiling = findCeiling(nums, candidate); return ceiling - floor - 1 > nums.length / 4; } private int findFloor(int[] nums, int candidate) { if (nums[nums.length - 1] < candidate) { return nums.length - 1; } if (nums[0] >= candidate) { return -1; } int l = 0; int r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] < candidate) { if (mid + 1 < nums.length && nums[mid + 1] >= candidate) { return mid; } else { l = mid + 1; } } else { if (mid - 1 >= 0 && nums[mid - 1] < candidate) { return mid - 1; } else { r = mid - 1; } } } return -1; } private int findCeiling(int[] nums, int candidate) { if (nums[nums.length - 1] <= candidate) { return nums.length; } if (nums[0] > candidate) { return 0; } int l = 0; int r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] <= candidate) { if (mid + 1 < nums.length && nums[mid + 1] > candidate) { return mid + 1; } else { l = mid + 1; } } else { if (mid - 1 >= 0 && nums[mid - 1] <= candidate) { return mid; } else { r = mid - 1; } } } return -1; }