forked from leetcoders/LeetCode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMajorityElement.java
More file actions
51 lines (48 loc) · 2.08 KB
/
MajorityElement.java
File metadata and controls
51 lines (48 loc) · 2.08 KB
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
/*
Author: King, wangjingui@outlook.com
Date: Dec 20, 2014
Problem: Majority Element
Difficulty: Easy
Source: https://oj.leetcode.com/problems/majority-element/
Notes:
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.
Solution: 1. Runtime: O(n) — Moore voting algorithm: We maintain a current candidate and a counter initialized to 0. As we iterate the array, we look at the current element x:
If the counter is 0, we set the current candidate to x and the counter to 1.
If the counter is not 0, we increment or decrement the counter based on whether x is the current candidate.
After one pass, the current candidate is the majority element. Runtime complexity = O(n).
2. Runtime: O(n) — Bit manipulation: We would need 32 iterations, each calculating the number of 1's for the ith bit of all n numbers. Since a majority must exist, therefore, either count of 1's > count of 0's or vice versa (but can never be equal). The majority number’s ith bit must be the one bit that has the greater count.
*/
public class Solution {
public int majorityElement_1(int[] num) {
int n = num.length;
if (n == 0) return 0;
if (n == 1) return num[0];
int res = num[0], cnt = 1;
for (int i = 1; i < n; ++i) {
if (cnt == 0) {
res = num[i];
++cnt;
continue;
}
if (res == num[i]) ++cnt;
else --cnt;
}
return res;
}
public int majorityElement_2(int[] num) {
int n = num.length;
if (n == 0) return 0;
if (n == 1) return num[0];
int res = 0;
for (int i = 0; i < 32; ++i) {
int one = 0, zero = 0;
for (int j = 0; j < n; ++j) {
if (((num[j]>>i) & 1) == 1) ++one;
else ++zero;
}
if (one > zero) res = res | (1<<i);
}
return res;
}
}