# Majority Number II ### Source - leetcode: [Majority Element II | LeetCode OJ](https://leetcode.com/problems/majority-element-ii/) - lintcode: [(47) Majority Number II](http://www.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. Example Given [1, 2, 1, 2, 1, 3, 3], return 1. Note There is only one majority number in the array. Challenge O(n) time and O(1) extra space. ~~~ ### 題解 題 [Majority Number](http://algorithm.yuanbin.me/zh-cn/math_and_bit_manipulation/majority_number.html) 的升級版，之前那道題是『兩兩抵消』，這道題自然則需要『三三抵消』，不過『三三抵消』需要注意不少細節，比如兩個不同數的添加順序和添加條件。 ### Java ~~~ public class Solution { /** * @param nums: A list of integers * @return: The majority number that occurs more than 1/3 */ 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; } } ~~~ ### 源碼分析 首先處理`count == 0`的情況，這里需要注意的是`count2 == 0 && key1 = num`, 不重不漏。最后再次遍歷原數組也必不可少，因為由于添加順序的區別，count1 和 count2的大小只具有相對意義，還需要最后再次比較其真實計數器值。 ### 復雜度分析 時間復雜度 O(n)O(n)O(n), 空間復雜度 O(2×2)=O(1)O(2 \times 2) = O(1)O(2×2)=O(1). ### Reference - [Majority Number II 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/majority-number-ii/)