Majority Number II

Question

• leetcode: Majority Element II | LeetCode OJ

• lintcode: (47) Majority Number II

  1. Given an array of integers,
     2. the majority number is the number that occurs more than 1/3 of the size of the array.
     3. 4. Find it.
     4. 6. Example
     5. Given [1, 2, 1, 2, 1, 3, 3], return 1.
     6. 9. Note
     7. There is only one majority number in the array.
     8. 12. Challenge
     9. O(n) time and O(1) extra space.

题解

题 Majority Number 的升级版，之前那道题是『两两抵消』，这道题自然则需要『三三抵消』，不过『三三抵消』需要注意不少细节，比如两个不同数的添加顺序和添加条件。

C++

  1. class Solution {
    2. public:
    3.     /**
    4.      * @param nums: A list of integers
    5.      * @return: The majority number occurs more than 1/3.
    6.      */
    7.     int majorityNumber(vector<int> nums) {
    8.         if (nums.empty()) return -1;
    9.   10.         int k1 = 0, k2 = 0, c1 = 0, c2 = 0;
    11.         for (auto n : nums) {
    12.             if (!c1 || k1 == n) {
    13.                 k1 = n;
    14.                 c1++;
    15.             } else if (!c2 || k2 == n) {
    16.                 k2 = n;
    17.                 c2++;
    18.             } else {
    19.                 c1--;
    20.                 c2--;
    21.             }
    22.         }
    23.   24.         c1 = 0; 
    25.         c2 = 0;
    26.         for (auto n : nums) {
    27.             if (n == k1) c1++;
    28.             if (n == k2) c2++;
    29.         }
    30.         return c1 > c2 ? k1 : k2;
    31.     }
    32. };

Java

  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.         if (nums == null || nums.isEmpty()) return -1;
    8.   9.         // pair
    10.         int key1 = -1, key2 = -1;
    11.         int count1 = 0, count2 = 0;
    12.         for (int num : nums) {
    13.             if (count1 == 0) {
    14.                 key1 = num;
    15.                 count1 = 1;
    16.                 continue;
    17.             } else if (count2 == 0 && key1 != num) {
    18.                 key2 = num;
    19.                 count2 = 1;
    20.                 continue;
    21.             }
    22.             if (key1 == num) {
    23.                 count1++;
    24.             } else if (key2 == num) {
    25.                 count2++;
    26.             } else {
    27.                 count1--;
    28.                 count2--;
    29.             }
    30.         }
    31.   32.         count1 = 0;
    33.         count2 = 0;
    34.         for (int num : nums) {
    35.             if (key1 == num) {
    36.                 count1++;
    37.             } else if (key2 == num) {
    38.                 count2++;
    39.             }
    40.         }
    41.         return count1 > count2 ? key1 : key2;
    42.     }
    43. }

源码分析

首先处理count == 0的情况，这里需要注意的是count2 == 0 && key1 = num, 不重不漏。最后再次遍历原数组也必不可少，因为由于添加顺序的区别，count1 和 count2的大小只具有相对意义，还需要最后再次比较其真实计数器值。

复杂度分析

时间复杂度 O(n), 空间复杂度 O(2 \times 2) = O(1).

Reference

• Majority Number II 参考程序 Java/C++/Python