一個整型陣列里除了兩個數字之外，其他的數字都出現了兩次，請寫程式找出這兩個只出現一次的數字
解題思路
最簡單的就是使用 HashMap，遍歷一遍陣列，用 map 記錄出現的次數，然后再遍歷一遍陣列，找出出現一次的數字
// num1,num2 分別為長度為 1 的陣列，傳出引數
// 將 num1[0],num2[0] 設定為回傳結果
import java.util.Map;
import java.util.HashMap;
public class Solution {
private Map<Integer, Integer> map = new HashMap<>();
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
for(int i = 0; i < array.length; i++) {
if(!map.containsKey(array[i])) {
map.put(array[i], 1);
} else {
map.put(array[i], map.get(array[i]) + 1);
}
}
for(int i = 0; i < array.length; i++) {
if(map.get(array[i]) == 1) {
if(num1[0] == 0) {
num1[0] = array[i];
} else {
num2[0] = array[i];
}
}
}
}
}
還可以使用位運演算法，首先要了解一下異或運算：
- n^0 = n
- n^n = 0
- nnm = n(nm)
我們可以讓陣列中的每一個數異或一下，最后會得到一個結果，就是兩個出現一次的數字的異或結果，我們找出該結果二進制中為 1 的位置 i，因為 1 一定是由 0，1 異或而來，因此要求得兩個數中，一定有一個數的二進制中的第 i 個位置為 1， 一個為 0，然后把這兩個組按照最開始的思路，依次異或，剩余的兩個結果就是這兩個只出現一次的數字，
// num1,num2 分別為長度為 1 的陣列，傳出引數
// 將 num1[0],num2[0] 設定為回傳結果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array.length == 2) {
num1[0] = array[0];
num2[0] = array[1];
}
// 用 bitResult 保存每次異或的結果
int bitResult = 0;
for(int i = 0; i < array.length; i++) {
bitResult ^= array[i];
}
// 找出位數為 1 的位置
int index = 0;
while((bitResult & 1) != 1) {
bitResult >>= 1;
index++;
}
// 將原陣列分成兩部分，分別包含一個不重復的數字，依據之前的方法再次遍歷找出
for(int i = 0; i < array.length; i++) {
if(((array[i] >> index) & 1) == 1) {
num1[0] ^= array[i];
} else {
num2[0] ^= array[i];
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/184926.html
標籤：其他