|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | | -/** |
4 | | - * 169. Majority Element |
5 | | -
|
6 | | - Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. |
7 | | - You may assume that the array is non-empty and the majority element always exist in the array. |
8 | | -
|
9 | | - Example 1: |
10 | | - Input: [3,2,3] |
11 | | - Output: 3 |
12 | | -
|
13 | | - Example 2: |
14 | | - Input: [2,2,1,1,1,2,2] |
15 | | - Output: 2 |
16 | | - */ |
17 | 3 | publicclass_169 { |
18 | | -publicstaticclassSolution1 { |
19 | | -/**Moore Voting Algorithm |
20 | | - * How to understand this: |
21 | | - * 1. For a number to qualify as a majority element, it needs to occur more than 1/2 times, which |
22 | | - * means there are a max of only one such element in any given array. |
23 | | - * 2. E.g. given this array [1,2,3,1,1,1], two of the 1s will be balanced off by 2 and 3, still there are two 1s remaining in the end |
24 | | - * which is the majority element*/ |
25 | | -publicintmajorityElement(int[]nums) { |
26 | | -intcount =1; |
27 | | -intmajority =nums[0]; |
28 | | -for (inti =1;i <nums.length;i++) { |
29 | | -if (count ==0) { |
30 | | -count++; |
31 | | -majority =nums[i]; |
32 | | - }elseif (nums[i] ==majority) { |
33 | | -count++; |
34 | | - }else { |
35 | | -count--; |
| 4 | +publicstaticclassSolution1 { |
| 5 | +/** |
| 6 | + * Moore Voting Algorithm |
| 7 | + * How to understand this: |
| 8 | + * 1. For a number to qualify as a majority element, it needs to occur more than 1/2 times, which |
| 9 | + * means there are a max of only one such element in any given array. |
| 10 | + * 2. E.g. given this array [1,2,3,1,1,1], two of the 1s will be balanced off by 2 and 3, still there are two 1s remaining in the end |
| 11 | + * which is the majority element |
| 12 | + */ |
| 13 | +publicintmajorityElement(int[]nums) { |
| 14 | +intcount =1; |
| 15 | +intmajority =nums[0]; |
| 16 | +for (inti =1;i <nums.length;i++) { |
| 17 | +if (count ==0) { |
| 18 | +count++; |
| 19 | +majority =nums[i]; |
| 20 | + }elseif (nums[i] ==majority) { |
| 21 | +count++; |
| 22 | + }else { |
| 23 | +count--; |
| 24 | + } |
| 25 | + } |
| 26 | +returnmajority; |
36 | 27 | } |
37 | | - } |
38 | | -returnmajority; |
39 | 28 | } |
40 | | - } |
41 | 29 |
|
42 | | -publicstaticclassSolution2 { |
43 | | -//bit manipulation |
44 | | -publicintmajorityElement(int[]nums) { |
45 | | -int[]bit =newint[32];//because an integer is 32 bits, so we use an array of 32 long |
46 | | -for (intnum :nums) { |
47 | | -for (inti =0;i <32;i++) { |
48 | | -if ((num >> (31 -i) &1) ==1) { |
49 | | -bit[i]++;//this is to compute each number's ones frequency |
50 | | - } |
| 30 | +publicstaticclassSolution2 { |
| 31 | +//bit manipulation |
| 32 | +publicintmajorityElement(int[]nums) { |
| 33 | +int[]bit =newint[32];//because an integer is 32 bits, so we use an array of 32 long |
| 34 | +for (intnum :nums) { |
| 35 | +for (inti =0;i <32;i++) { |
| 36 | +if ((num >> (31 -i) &1) ==1) { |
| 37 | +bit[i]++;//this is to compute each number's ones frequency |
| 38 | + } |
| 39 | + } |
| 40 | + } |
| 41 | +intres =0; |
| 42 | +//this below for loop is to construct the majority element: since every bit of this element would have appeared more than n/2 times |
| 43 | +for (inti =0;i <32;i++) { |
| 44 | +bit[i] =bit[i] >nums.length /2 ?1 |
| 45 | + :0;//we get rid of those that bits that are not part of the majority number |
| 46 | +res +=bit[i] * (1 << (31 -i)); |
| 47 | + } |
| 48 | +returnres; |
51 | 49 | } |
52 | | - } |
53 | | -intres =0; |
54 | | -//this below for loop is to construct the majority element: since every bit of this element would have appeared more than n/2 times |
55 | | -for (inti =0;i <32;i++) { |
56 | | -bit[i] =bit[i] >nums.length /2 ?1 |
57 | | - :0;//we get rid of those that bits that are not part of the majority number |
58 | | -res +=bit[i] * (1 << (31 -i)); |
59 | | - } |
60 | | -returnres; |
61 | 50 | } |
62 | | - } |
63 | 51 | } |