[LeetCode] 229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

求众数II。题意跟版本一差不多，在数组里找所有出现次数大于1/3数组长度的元素。

题目要求时间O(n)，空间O(1)，所以思路还是投票法。对于一个数组，最多只有两个元素的出现次数超过数组长度的三分之一，所以我们这里创建两个candidate。首先我们将这两个candidate初始化为0（因为有一些test case是数组长度小于2的所以不能设置为nums[0], nums[1]），然后遍历数组，按照版本一的做法，统计或者更新两个candidate的出现次数。这一题需要遍历两次input数组，第二次遍历的时候是在验证找到的两个candidate是否出现次数真的大于数组长度的三分之一，若是则加入结果集。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public List<Integer> majorityElement(int[] nums) {
 3         List<Integer> res = new ArrayList<>();
 4         // corner case
 5         if (nums == null || nums.length == 0) {
 6             return res;
 7         }
 8 
 9         // normal case
10         int candidate1 = 0;
11         int candidate2 = 0;
12         int count1 = 0;
13         int count2 = 0;
14         for (int num : nums) {
15             if (num == candidate1) {
16                 count1++;
17             } else if (num == candidate2) {
18                 count2++;
19             } else if (count1 == 0) {
20                 candidate1 = num;
21                 count1++;
22             } else if (count2 == 0) {
23                 candidate2 = num;
24                 count2++;
25             } else {
26                 count1--;
27                 count2--;
28             }
29         }
30 
31         count1 = 0;
32         count2 = 0;
33         for (int num : nums) {
34             if (num == candidate1) {
35                 count1++;
36             } else if (num == candidate2) {
37                 count2++;
38             }
39         }
40         if (count1 > nums.length / 3) {
41             res.add(candidate1);
42         }
43         if (count2 > nums.length / 3) {
44             res.add(candidate2);
45         }
46         return res;
47     }
48 }

JavaScript实现

 1 /**
 2  * @param {number[]} nums
 3  * @return {number[]}
 4  */
 5 var majorityElement = function (nums) {
 6     let res = [];
 7     // corner case
 8     if (nums === null || nums.length === 0) {
 9         return res;
10     }
11     // normal case
12     let candidate1 = 0;
13     let candidate2 = 0;
14     let count1 = 0;
15     let count2 = 0;
16     for (let num of nums) {
17         if (num === candidate1) {
18             count1++;
19         } else if (num === candidate2) {
20             count2++;
21         } else if (count1 === 0) {
22             candidate1 = num;
23             count1++;
24         } else if (count2 === 0) {
25             candidate2 = num;
26             count2++;
27         } else {
28             count1--;
29             count2--;
30         }
31     }
32 
33     count1 = 0;
34     count2 = 0;
35     for (let num of nums) {
36         if (num === candidate1) {
37             count1++;
38         } else if (num === candidate2) {
39             count2++;
40         }
41     }
42     if (count1 > Math.floor(nums.length / 3)) {
43         res.push(candidate1);
44     }
45     if (count2 > Math.floor(nums.length / 3)) {
46         res.push(candidate2);
47     }
48     return res;
49 };