剑指offer(40)数组中只出现一次的数字

时间:2022-11-23 19:02:02

题目描述

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

题目分析

第一种方法:使用js中的indexOf()和lastIndexOf(),只要两个相等,就是只出现一次的数。

第二种方法:使用map记录下每个数的次数,占空间。

第三种方法:根据异或结果中1所在的二进制位数,把数组中数分成两种不同类别,分别异或得出结果。

  重点介绍下第三种方法,位运算中异或的性质:两个相同数字异或=0一个数和0异或还是它本身

  当只有一个数出现一次时,我们把数组中所有的数,依次异或运算,最后剩下的就是落单的数,因为成对儿出现的都抵消了。

  依照这个思路,我们来看两个数(我们假设是AB)出现一次的数组。我们首先还是先异或,剩下的数字肯定是A、B异或的结果,

  这个结果的二进制中的1,表现的是A和B的不同的位

  我们就取异或的结果中第一个1所在的位数,假设是第3位,接着把原数组分成两组,通过比较第3位是否为1来分成两组。

  如此,相同的数肯定在一个组,因为相同数字所有位都相同,而不同的数,肯定不在一组

  然后把这两个组按照最开始的思路,依次异或,剩余的两个结果就是这两个只出现一次的数字。

代码

第一种:

// 第一种
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;
}