-
Notifications
You must be signed in to change notification settings - Fork 90
/
SingleNumberII137.java
39 lines (36 loc) · 1.23 KB
/
SingleNumberII137.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
/**
* Given an array of integers, every element appears three times except for
* one, which appears exactly once. Find that single one.
*
* Note:
* Your algorithm should have a linear runtime complexity. Could you implement
* it without using extra memory?
*/
public class SingleNumberII137 {
/**
* https://leetcode.com/problems/single-number-ii/discuss/43294/Challenge-me-thx
* https://leetcode.com/problems/single-number-ii/discuss/43295/Detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers
*/
public int singleNumber(int[] A) {
int ones = 0, twos = 0;
for(int i = 0; i < A.length; i++){
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
}
return ones;
}
/**
* https://leetcode.com/problems/single-number-ii/discuss/43363/JAVA-Easy-Version-To-UnderStand!!!!!!!!!!!!!!!!!!!
*/
public int singleNumber2(int[] nums) {
int len = nums.length, result = 0;
for (int i = 0; i < 32; i++) {
int sum = 0;
for (int j = 0; j < len; j++) {
sum += (nums[j] >> i) & 1;
}
result |= (sum % 3) << i;
}
return result;
}
}