2018-06-17 14:04:27
問題描述：
問題求解：
方法一、如果對空間復雜度沒有要求，那么直接使用HashMap對每個數字出現次數進行計數，最后對HashMap遍歷一遍即可，總的時間復雜度為O(n)，空間開銷較大。
方法二、對空間要求比較嚴格的話，那就只能使用位運算了，一個簡明的思路是，對于所有出現三次的數，其各個位置上1出現的次數也是3的倍數，可以利用這點來進行判斷。
public class SingleNumberII {public int singleNumber(int[] nums) {int res = 0;for (int i = 0; i < 32; i++) {int mask = 1;int cnt = 0;mask = mask << i;for (int j = 0; j < nums.length; j++) {if ((nums[j] & mask) != 0) cnt++;}if (cnt % 3 != 0) res |= mask;}return res;}
}
方法三、上面的解法系數較大，可以進一步對其簡化。核心思路依然是位運算，這里引入兩個變量，ones 和 twos。ones:記錄到當前計算的變量為止，二進制1出現“1次”（mod 3 之后的 1）的數位。
twos:記錄到當前計算的變量為止，二進制1出現“2次”（mod 3 之后的 2）的數位。
當ones和twos中的某一位同時為1時表示二進制1出現3次，此時需要清零。即用二進制模擬三進制計算。最終ones記錄的是最終結果。
public int singleNumberII(int[] nums) {int ones = 0;int twos = 0;int xthree = 0;for (int num : nums) {twos |= (ones & num);ones ^= num;xthree = ~(twos & ones);ones &= xthree;twos &= xthree;}return ones;}
?
)
