<div id="div40"><h4> 40, 数组中只出现一次的数字 <h4></div> 一个整型数组里除了**两个**数字之外，其他的数字都出现了**两次**。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1) **任何一个数字异或它自己都等于0，而0异或任何数都等于那个数** **把数组分成两个子数组，使每个子数组包含一个只出现一次的数字，而其他数字成对出现** 举例：{2,4,3,6,3,2,5,5} - 我们依次对数组中的每个数字做异或运行之后，得到的结果用二进制表示是0010。 - 异或得到结果中的倒数第二位是1，于是我们根据数字的倒数第二位是不是1分为两个子数组。 - 第一个子数组{2,3,6,3,2}中所有数字的倒数第二位都是1，而第二个子数组{4,5,5}中所有数字的倒数第二位都是0。 - 接下来只要分别两个子数组求异或，就能找到第一个子数组中只出现一次的数字是6，而第二个子数组中只出现一次的数字是4。 ```javascript // 第一种: indexOf是从前向后查 而lastIndexOf是从后向前查 但是二者返回索引都为下标 function FindNumsAppearOnce(array) { const res = []; for (let i = 0; i < array.length; i++) { if (array.indexOf(array[i]) === array.lastIndexOf(array[i])) { res.push(array[i]); } } return res; } // 第二种 function FindNumsAppearOnce2(array) { const map = {}, res = []; for (let i = 0; i < array.length; i++) { if (!map[array[i]]) { map[array[i]] = 1; } else { map[array[i]]++; } } for (let i = 0; i < array.length; i++) { if (map[array[i]] === 1) { res.push(array[i]); } } return res; } // 第三种 function FindNumsAppearOnce3(array) { let tmp = array[0]; for (let i = 1; i < array.length; i++) { tmp = tmp ^ array[i]; } if (tmp === 0) return; let index = 0; // 记录第几位是1 while ((tmp & 1) === 0) { tmp = tmp >> 1; index++; } let num1 = 0, num2 = 0; for (let i = 0; i < array.length; i++) { if (isOneAtIndex(array[i], index)) num1 = num1 ^ array[i]; else num2 = num2 ^ array[i]; } return [num1, num2]; } function isOneAtIndex(num, index) { num = num >> index; return num & 1; } ```