題目描述
在一個數(shù)組 nums 中除一個數(shù)字只出現(xiàn)一次之外捺典，其他數(shù)字都出現(xiàn)了三次从祝。請找出那個只出現(xiàn)一次的數(shù)字。
題解一
先將數(shù)組排序牍陌，然后再找出現(xiàn)一次的數(shù)字是比較簡單的。
時間復雜度為退客，空間復雜度為
链嘀。比較簡單，代碼省略怀泊。
題解二
還有一種想法是以空間換時間误趴，使用一個哈希表來記錄數(shù)組中每個數(shù)字出現(xiàn)的次數(shù)，最終可以得到兩個只出現(xiàn)一次的數(shù)字凉当。
時間復雜度為，空間復雜度為
看杭。比較簡單，代碼省略楼雹。
題解三
如果需要繼續(xù)優(yōu)化時空復雜度應該怎么做呢模孩？這里可以沿用上一題的思路，使用位運算來解決榨咐。將所有數(shù)字的二進制表示的每一位都進行相加，如果某一位的和能夠被3整除块茁，那么那個只出現(xiàn)一次的數(shù)字在這個位上就是0；若不能整除胃夏，那么那個只出現(xiàn)一次的數(shù)字在這個位上就是1昌跌。
下面是參考代碼：
import java.math.BigInteger;
class Solution {
public int singleNumber(int[] nums) {
StringBuilder sb = new StringBuilder(getFullBinaryString(0));
for (int num : nums) {
String numString = getFullBinaryString(num);
for (int i = 0; i < 32; i++) {
sb.setCharAt(i, (char) (sb.charAt(i)+numString.charAt(i)-'0'));
}
}
for (int i = 0; i < 32; i++) {
if ((int) (sb.charAt(i)) % 3 == 0)
sb.setCharAt(i, '0');
else sb.setCharAt(i, '1');
}
return Integer.valueOf(sb.toString(), 2);
}
public String getFullBinaryString(int num) {
String s = Integer.toBinaryString(num);
return String.format("%032d", new BigInteger(s));
}
}
可以將這道題擴展一下，若題目更改為：在一個數(shù)組 nums 中除一個數(shù)字只出現(xiàn)一次之外答恶，其他數(shù)字都出現(xiàn)了n次。請找出那個只出現(xiàn)一次的數(shù)字悬嗓。其實解法是相同的裕坊，具體的代碼就不寫啦~
