題目一：數(shù)組中只出現(xiàn)一次的兩個數(shù)字。
一個整型數(shù)組里除了兩個數(shù)字之外来氧，其他的數(shù)字都出現(xiàn)了兩次纳令。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字帮孔。要求時間復(fù)雜度是 O(n)，空間復(fù)雜度是 O(1)类缤。
練習(xí)地址
https://www.nowcoder.com/practice/e02fdb54d7524710a7d664d082bb7811
https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
參考答案
我們從頭到尾依次異或數(shù)組中的每個數(shù)字臼勉，那么最終得到的結(jié)果就是兩個只出現(xiàn)一次的數(shù)字的異或結(jié)果，因為其他數(shù)字都出現(xiàn)了兩次呀非，在異或中全部抵消了坚俗。由于這兩個數(shù)字肯定不一樣镜盯，那么異或的結(jié)果肯定不為 0岸裙，也就是說，在這個結(jié)果數(shù)字的二進制表示中至少有一位為 1速缆。我們在結(jié)果數(shù)字中找到第一個為 1 的位的位置降允，記為第 n 位。現(xiàn)在我們以第 n 位是不是 1 為標準把原數(shù)組中的數(shù)字分成兩個子數(shù)組艺糜，第一個子數(shù)組中每個數(shù)字的第 n 位都是 1剧董，而第二個子數(shù)組中每個數(shù)字的第 n 位都是 0幢尚。
由于我們分組的標準是數(shù)字中的某一位是 1 還是 0，那么出現(xiàn)了兩次的數(shù)字肯定被分配到同一個子數(shù)組翅楼。因為兩個相同的數(shù)字的任意一位都是相同的尉剩，我們不可能把兩個相同的數(shù)字分配到兩個子數(shù)組中去，于是我們已經(jīng)把原數(shù)組分成了兩個子數(shù)組毅臊，每個子數(shù)組都包含一個只出現(xiàn)一次的數(shù)字理茎，而其他數(shù)字都出現(xiàn)了兩次。
我們已經(jīng)知道如何在數(shù)組中找出唯一一個只出現(xiàn)一次的數(shù)字管嬉，因此皂林，到此為止所有的問題都已經(jīng)解決了。
下面是參考代碼：
// num1,num2分別為長度為1的數(shù)組蚯撩。傳出參數(shù)
// 將num1[0],num2[0]設(shè)置為返回結(jié)果
public class Solution {
public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2) {
if (array == null || array.length < 2) {
return;
}
int xor = 0;
for (int num : array) {
xor ^= num;
}
int index = 0;
while (xor > 0 && (xor & 1) == 0) {
xor >>= 1;
index++;
}
for (int num : array) {
if (((num >> index) & 1) > 0) {
num1[0] ^= num;
} else {
num2[0] ^= num;
}
}
}
}
復(fù)雜度分析
- 時間復(fù)雜度：O(n)础倍。
- 空間復(fù)雜度：O(1)。
題目二：數(shù)組中唯一只出現(xiàn)一次的數(shù)字胎挎。
在一個數(shù)組中除一個數(shù)字只出現(xiàn)一次之外沟启，其他數(shù)字都出現(xiàn)了三次。請找出那個只出現(xiàn)一次的數(shù)字犹菇。
練習(xí)地址
劍指 Offer 56 - II. 數(shù)組中數(shù)字出現(xiàn)的次數(shù) II - 力扣（LeetCode） (leetcode-cn.com)
參考答案
class Solution {
public int singleNumber(int[] nums) {
if (nums == null) {
return 0;
}
int[] bitSum = new int[32];
for (int i = 0; i < nums.length; i++) {
int bitMask = 1;
for (int j = 31; j >= 0; j--) {
if ((nums[i] & bitMask) != 0) {
bitSum[j]++;
}
bitMask <<= 1;
}
}
int result = 0;
for (int i = 0; i < 32; i++) {
result <<= 1;
result += bitSum[i] % 3;
}
return result;
}
}
復(fù)雜度分析
- 時間復(fù)雜度：O(n)美浦。
- 空間復(fù)雜度：O(1)。
