|
3 | 3 | importjava.util.ArrayList; |
4 | 4 | importjava.util.List; |
5 | 5 |
|
6 | | -/** |
7 | | - * 229. Majority Element II |
8 | | - * |
9 | | - * Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. |
10 | | - * The algorithm should run in linear time and in O(1) space. |
11 | | - * |
12 | | - * Example 1: |
13 | | - * Input: [3,2,3] |
14 | | - * Output: [3] |
15 | | - * |
16 | | - * Example 2: |
17 | | - * Input: [1,1,1,3,3,2,2,2] |
18 | | - * Output: [1,2] |
19 | | -
|
20 | | - Hint: |
21 | | - How many majority elements could it possibly have? |
22 | | - Do you have a better hint? Suggest it! |
23 | | - */ |
24 | 6 | publicclass_229 { |
25 | 7 |
|
26 | 8 | publicstaticclassSolution1 { |
27 | | -/**Moore Voting algorithm: |
| 9 | +/** |
| 10 | + * Moore Voting algorithm: |
28 | 11 | * This is an extension of Majority Element I, instead of one one majority, there could be a max of two majority elements, |
29 | | - * so we'll just use two counters to do the job.*/ |
| 12 | + * so we'll just use two counters to do the job. |
| 13 | + */ |
30 | 14 | publicList<Integer>majorityElement(int[]nums) { |
31 | 15 | List<Integer>result =newArrayList<>(); |
32 | 16 | if (nums ==null ||nums.length ==0) { |
|