Majority Number

Question

  1. Given an array of integers, the majority number is
  2. the number that occurs more than half of the size of the array. Find it.
  4. Example
  5. Given [1, 1, 1, 1, 2, 2, 2], return 1
  7. Challenge
  8. O(n) time and O(1) extra space

题解

找出现次数超过一半的数，使用哈希表统计不同数字出现的次数，超过二分之一即返回当前数字。这种方法非常简单且容易实现，但会占据过多空间，注意到题中明确表明要找的数会超过二分之一，这里的隐含条件不是那么容易应用。既然某个数超过二分之一，那么用这个数和其他数进行 PK，不同的计数器都减一（核心在于两两抵消），相同的则加1，最后返回计数器大于0的即可。综上，我们需要一辅助数据结构如pair<int, int>.

C++

  1. int majorityNumber(vector<int> nums) {
  2.     if (nums.empty()) return -1;
  4.     int k = -1, count = 0;
  5.     for (auto n : nums) {
  6.         if (!count) k = n;
  7.         if (k == n) count++;
  8.         else count--;
  9.     }
  10.     return k;
  11. }

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: a list of integers
  4.      * @return: find a  majority number
  5.      */
  6.     public int majorityNumber(ArrayList<Integer> nums) {
  7.         if (nums == null || nums.isEmpty()) return -1;
  9.         // pair<key, count>
  10.         int key = -1, count = 0;
  11.         for (int num : nums) {
  12.             // re-initialize
  13.             if (count == 0) {
  14.                 key = num;
  15.                 count = 1;
  16.                 continue;
  17.             }
  18.             // increment/decrement count
  19.             if (key == num) {
  20.                 count++;
  21.             } else {
  22.                 count--;
  23.             }
  24.         }
  26.         return key;
  27.     }
  28. }

源码分析

初始化count = 0, 遍历数组时需要先判断count == 0以重新初始化。

复杂度分析

时间复杂度 O(n), 空间复杂度 O(1).