首页 > 代码库 > Lintcode: Majority Number II 解题报告
Lintcode: Majority Number II 解题报告
Majority Number II
原题链接： http://lintcode.com/en/problem/majority-number-ii/#
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.
There is only one majority number in the array
For [1, 2, 1, 2, 1, 3, 3] return 1
O(n) time and O(1) space
SOLUTION 1:
与Majority Number 1相似。但我们要保存2个number.
1. 遇到第一个不同的值，先记录number 2.
2. 新值与n1,n2都不同，则cnt1,cnt2都减少
3. 当n1,n2任意一个为0时，从新值中挑出一个记录下来。
4. 最后再对2个候选值进行查验，得出最终的解。
主页君其实也想不太明白这个题目为什么这样解。
还是举个例子吧
7 1 7 7 61 61 61 10 10 10 61
n1 7 7 7 7 7 7 7 7 7 10 10
cnt1 1 1 2 3 2 2 2 1 0 1 1
n2 0 1 1 1 1 61 61 61 61 61 61
cnt2 0 1 1 1 0 1 2 1 0 0 1
证明：要对cnt1--的条件是：遇到2个与n1不同的值
1. 当n2为空时，第一个会填补n2, 第二个才会减cnt1.
2. 或者，n2已经被填补，这时会一直减cnt1，但是cnt2也会被减，当cnt2减到0,再遇到新值也不会再减了。也就是说，连续减n的情形，一定是前面连续
加过n2 n次(那n次连加n2时，不会减少cnt1)。
以上：2个与n1不同的值，才会对cnt1减。如果n1是majority值，它一定最后会留下 。
以上理论对于n2也适用。
1 public class Solution { 2 /** 3 * @param nums: A list of integers 4 * @return: The majority number that occurs more than 1/3 5 */ 6 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 }56 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/lintcode/math/MajorityNumber2.java
Lintcode: Majority Number II 解题报告