-
Notifications
You must be signed in to change notification settings - Fork 81
/
MajorityElement169.java
70 lines (61 loc) · 1.85 KB
/
MajorityElement169.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
* Given an array of size n, find the majority element. The majority element is
* the element that appears more than ⌊ n/2 ⌋ times.
*
* You may assume that the array is non-empty and the majority element always
* exist in the array.
*/
public class MajorityElement169 {
public int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int N = nums.length;
for (int i=0; i<N; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
if (map.get(nums[i]) > (N/2)) {
return nums[i];
}
}
return nums[0];
}
/**
* https://discuss.leetcode.com/topic/8692/o-n-time-o-1-space-fastest-solution
* Moore voting algorithm
*/
public int majorityElement2(int[] num) {
int major=num[0], count = 1;
for(int i=1; i<num.length;i++){
if(count==0){
count++;
major=num[i];
}else if(major==num[i]){
count++;
}else count--;
}
return major;
}
/**
* https://discuss.leetcode.com/topic/28601/java-solutions-sorting-hashmap-moore-voting-bit-manipulation
* Sorting
*/
public int majorityElement3(int[] num) {
Arrays.sort(num);
return num[num.length/2];
}
/**
* https://discuss.leetcode.com/topic/28601/java-solutions-sorting-hashmap-moore-voting-bit-manipulation
* Bit manipulation
*/
public int majorityElement4(int[] nums) {
int[] bit = new int[32];
for (int num: nums)
for (int i=0; i<32; i++)
if ((num>>(31-i) & 1) == 1)
bit[i]++;
int ret=0;
for (int i=0; i<32; i++) {
bit[i]=bit[i]>nums.length/2?1:0;
ret += bit[i]*(1<<(31-i));
}
return ret;
}
}