Majority Number II

Question

  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.
  4. Find it.
  6. Example
  7. Given [1, 2, 1, 2, 1, 3, 3], return 1.
  9. Note
  10. There is only one majority number in the array.
  12. Challenge
  13. 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;
  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.         }
  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;
  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.         }
  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