# Majority Number ### Source - leetcode: [Majority Element | LeetCode OJ](https://leetcode.com/problems/majority-element/) - lintcode: [(46) Majority Number](http://www.lintcode.com/en/problem/majority-number/) ~~~ Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it. Example Given [1, 1, 1, 1, 2, 2, 2], return 1 Challenge O(n) time and O(1) extra space ~~~ ### 題解 找出現次數超過一半的數，使用哈希表統計不同數字出現的次數，超過二分之一即返回當前數字。這種方法非常簡單且容易實現，但會占據過多空間，注意到題中明確表明要找的數會超過二分之一，這里的隱含條件不是那么容易應用。既然某個數超過二分之一，那么用這個數和其他數進行 PK，不同的計數器都減一**（核心在于兩兩抵消）**，相同的則加1，最后返回計數器大于0的即可。綜上，我們需要一輔助數據結構如`pair<int, int>`. ### Java ~~~ public class Solution { /** * @param nums: a list of integers * @return: find a majority number */ public int majorityNumber(ArrayList<Integer> nums) { if (nums == null || nums.isEmpty()) return -1; // pair<key, count> int key = -1, count = 0; for (int num : nums) { // re-initialize if (count == 0) { key = num; count = 1; continue; } // increment/decrement count if (key == num) { count++; } else { count--; } } return key; } } ~~~ ### 源碼分析 初始化`count = 0`, 遍歷數組時需要先判斷`count == 0`以重新初始化。 ### 復雜度分析 時間復雜度 O(n)O(n)O(n), 空間復雜度 O(1)O(1)O(1).