Majority Element II 解答

Question

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Majority Element I

A Linear Time Voting Algorithm

Solution 1 -- Binary Search

我们发现一个规律。如果是大于 1/k 的majority，排好序的数组中，它们可能出现的位置是

len / k, len * 2/ k, len * 3 / k, ...

所以我们可以依次用二分查找法查找在 len * i / k 的各个点的start和end position，然后算长度，判断是否满足条件。

动态一些的方法是下一个待判断点的坐标为 prevEnd + len / k + 1

如图，绿线为start point 红线为end point

Time complexity O(n log n), space O(1)

 1 public class Solution {
 2     public List<Integer> majorityElement(int[] nums) {
 3         Arrays.sort(nums);
 4         List<Integer> result = new ArrayList<Integer>();
 5         int len = nums.length;
 6         if (len < 1)
 7             return result;
 8         int candidate1 = nums[len / 3];
 9         // Find start and end of candidate1
10         int[] range1 = searchRange(nums, candidate1);
11         int num1 = range1[1] - range1[0] + 1;
12         if (num1 > len / 3)
13             result.add(candidate1);
14         // Find start and end of candidate2
15         int index = len / 3 + range1[1] + 1;
16         if (index >= len)
17             return result;
18         int candidate2 = nums[index];
19         int[] range2 = searchRange(nums, candidate2);
20         int num2 = range2[1] - range2[0] + 1;
21         if (num2 > len / 3 && candidate2 != candidate1)
22             result.add(candidate2);
23         return result;
24     }
25     
26     private int[] searchRange(int[] nums, int target) {
27         int start = 0, end = nums.length - 1, mid;
28         int[] result = new int[2];
29         result[0] = -1;
30         result[1] = -1;
31         while (start + 1 < end) {
32             mid = (end - start) / 2 + start;
33             if (nums[mid] >= target)
34                 end = mid;
35             else
36                 start = mid;
37         }
38         if (nums[start] == target)
39             result[0] = start;
40         else if (nums[end] == target)
41             result[0] = end;
42         
43         start = 0;
44         end = nums.length - 1;
45         
46         while (start + 1 < end) {
47             mid = (end - start) / 2 + start;
48             if (nums[mid] > target)
49                 end = mid;
50             else
51                 start = mid;
52         }
53         if (nums[end] == target)
54             result[1] = end;
55         else if (nums[start] == target)
56             result[1] = start;
57         return result;
58     }
59 }

Solution 2 -- Moore Voting Algorithm

Time complexity O(n), space cost O(1)

 1 public class Solution {
 2     public List<Integer> majorityElement(int[] nums) {
 3         int count1 = 0, count2 = 0;
 4         Integer num1 = null, num2 = null;
 5         int len = nums.length;
 6         for (int current : nums) {
 7             if (num1 != null && current == num1.intValue()) {
 8                 count1++;
 9             } else if (num2 != null && current == num2.intValue()) {
10                 count2++;
11             } else if (num1 == null || count1 == 0) {
12                 num1 = current;
13                 count1 = 1;
14             } else if (num2 == null || count2 == 0) {
15                 num2 = current;
16                 count2 = 1;
17             } else {
18                 count1--;
19                 count2--;
20             }
21         }
22         // Check whether num1, num2, num3 are valid
23         count1 = 0;
24         count2 = 0;
25         for (int current : nums) {
26             if (current == num1.intValue()) {
27                 count1++;
28             } else if (current == num2.intValue()) {
29                 count2++;
30             }
31         }
32         List<Integer> result = new ArrayList<Integer>();
33         if (count1 > len / 3) {
34             result.add(num1);
35         }
36         if (count2 > len / 3) {
37             result.add(num2);
38         }
39         return result;
40     }
41 }