Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
考慮全部用二進制表示,如果我們把 第 ith 個位置上所有數字的和對3取余,那麼只會有兩個結果 0 或 1 (根據題意,3個0或3個1相加余數都為0). 因此取余的結果就是那個 “Single Number”。
public class Solution {
public int singleNumber(int[] nums) {
int cnt[] = new int[32];
int single = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < nums.length; j++) {
cnt[i] += (nums[j] >> i) & 0x1;
}
single |= cnt[i] % 3 << i;
}
return single;
}
}
一種改進的做法是使用掩碼變量:
ones 代表第當第
Java:
// Runtime: 1 ms
public class Solution {
public int singleNumber(int[] nums) {
int ones = 0, twos = 0, threes = 0;
for (int i = 0; i < nums.length; i++) {
twos |= ones & nums[i];
ones ^= nums[i];
threes = ones & twos;
//對於ones 和 twos 把出現了3次的位置設置為0
ones &= ~threes;
twos &= ~threes;
}
return ones;
}
}