137. Single Number II (Medium)
https://leetcode.com/problems/single-number-ii/
Given a non-empty 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?
Example 1:
Input: [2,2,3,2] Output: 3
Example 2:
Input: [0,1,0,1,0,1,99] Output: 99
Solutions
1.
class Solution {
// Assume we sum up all nums bit by bit, we adopt 32 counter to count
// 1s on each bit. Since all the numbers appear thrice except one, for a specific bit,
// we can always mod 3 to get 1 if the special number carries 1 on that bit; in a similar way
// we can sort all the 0s on this special number.
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < 32; i++) {
int k = 1 << i;
int count = 0;
for (int j = 0; j < nums.length; j++) {
// can not use (nums[j] & k) > 0, there may be negative values
if ((nums[j] & k) != 0) {
count++;
}
}
ans += k * (count % 3);
}
return ans;
}
}
2.
class Solution {
// This solution is hacky. Memorize it or ignore it.
// See also: https://stackoverflow.com/questions/21297067/single-number-ii-from-leetcode
public int singleNumber(int[] A) {
int ones = 0;
int twos = 0;
for (int i = 0; i < A.length; i++) {
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
}
return ones;
}
}