首页 > 试题广场 >

数组中只出现一次的两个数字

[编程题]数组中只出现一次的两个数字

热度指数：119719 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围：数组长度 $2\le n \le 1000$ ，数组中每个数的大小 $0 < val \le 1000000$
要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

提示：输出时按非降序排列。

示例1

输入

[1,4,1,6]

输出

[4,6]

说明

返回的结果中较小的数排在前面

示例2

输入

[1,2,3,3,2,9]

输出

[1,9]

算法知识视频讲解

Javascript

Xinleidebaby

function FindNumsAppearOnce( array ) {
    // write code here
    let a=[]
    let map=new Map()
    for(let i=0;i<array.length;i++){
        if(map.get(array[i])==undefined) map.set(array[i],1);
        else {
            a.push(array[i])
        }
    }
 let c=array.filter(function(item,index){
        return !a.includes(item)
    })
 return c.sort((a,b)=>a-b)
}

发表于 2022-08-04 10:39:36 回复(0)

Javascript

卑微呀打工人

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型一维数组
 */
function FindNumsAppearOnce( array ) {
    // write code here
    let result = []
    let res = array.reduce((temp,data)=>{
       temp[data] = temp[data]? temp[data]+1:1
        return temp
    },{})
    for (index in res){
        if(res[index] == 1){
            result.push(index)
        }
    }
    return result.sort((a,b)=>{
        return a-b
    })
}
module.exports = {
    FindNumsAppearOnce : FindNumsAppearOnce
};

发表于 2022-06-30 16:39:02 回复(0)

Javascript

牛客Monica

function FindNumsAppearOnce( array ) {
    // write code here
    const map = new Map()
    const res = []
    for(const item of array){
        if(map.has(item)){
            let n = map.get(item)
            map.set(item,n+1)
        }else{
            map.set(item,1)
        }
    }
    map.forEach((value,key)=>{
        if(value === 1)
            res.push(key)
    })
    return res.sort()
}

发表于 2022-06-02 11:00:19 回复(0)

Javascript

怕浪猫

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型一维数组
 */
function FindNumsAppearOnce( array ) {
    // write code here
    let len = array.length
    let map = new Map()
    let res = []
    for(let i = 0; i <len; i++){
        if(map.has(array[i])){
            map.set(array[i],map.get(array[i])+1)
        }
        else map.set(array[i], 1)
    }
    map.forEach((value,key) => {
        if(value ==1) res.push(key)
    })
    return res.sort((a,b) => a-b)
}
module.exports = {
    FindNumsAppearOnce : FindNumsAppearOnce
};

发表于 2022-05-29 10:23:43 回复(0)

Javascript

萌萌94

function FindNumsAppearOnce( array ) {
// write code here
let a = array.reduce((a,b) => a^b);

// 通过lowbit将数组分为两组, 两组数分别累计异或运算得到两个数

let lowbit = a & (-a);
let left = [], right = [];
for (let item of array) {
if (item & lowbit) left.push(item);
else right.push(item);
}
let lv = left.reduce((a,b) => a^b, 0);
let rv = right.reduce((a,b) => a^b, 0);

if (lv < rv) return [lv, rv]
else return [rv, lv];
}

发表于 2022-05-27 08:37:18 回复(0)

Javascript

美英

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型一维数组
 */
function FindNumsAppearOnce( array ) {
    // write code here
    var list = [];
    var obj = {};
    array.forEach(item=>{
        if(obj[item]){
            obj[item]++
        }else{
            obj[item]=1
        }
    })
    let arr=[];
    console.log(obj);
    for(let i in obj){
        if(obj[i]==1){
            arr.push(i);
        }
    }
    return arr;
}
module.exports = {
    FindNumsAppearOnce : FindNumsAppearOnce
};

发表于 2021-11-12 16:20:39 回复(0)

Javascript

Veagau

利用indexof函数

function FindNumsAppearOnce( array ) {
    // write code here
    let arrTemp = [];
    array.sort((a,b)=>{return a-b});
    for(let item of array){
        if(array.indexOf(item)===array.lastIndexOf(item)){
            arrTemp.push(item);
        }
    }
    return arrTemp
}

发表于 2021-09-18 11:45:45 回复(0)

Javascript

17SKYE

function FindNumsAppearOnce( array ) {
    // write code here
    let result=[];
    while(array){
        let del=array.pop();
        if(array.indexOf(del)>-1){
            array.splice(array.indexOf(del),1);
        }
        else{
            result.push(del);
        }
        if(result.length>1) break;
    }
    if(result[1]<result[0]){
        result.unshift(result.pop());
    }
    return result;
}

pop和splice搭配，先pop出一个，用indexOf判断数组内还有没有，如果没有了说明就是只出现了一次的，把它保存在返回数组中，如果还有就说明出现了2次，使用splice删掉出现第二次出现的元素。直到返回数组result的长度大于1，跳出循环，并且给两个元素排序，得到最终结果。

发表于 2021-08-03 09:44:50 回复(0)

JavaScript

别卷啦！

function FindNumsAppearOnce( array ) {
    // write code here
    const map = new Map()
    const res = []
    for(let i of array){
        map[i] = (map[i] || 0) + 1
    }
    for(let i in map){
        if(map[i] == 1)
            res.push(i)
    }
   return  res[0] < res[1] ? res : [res[1], res[0]];
}

编辑于 2021-07-08 11:28:01 回复(0)

JavaScript

你有尾巴吗

function FindNumsAppearOnce( array ) {
	let res=[];
for(let x of array){
	if(array.indexOf(x)==array.lastIndexOf(x)){
		res.push(x)
	}
}
res.sort((a,b)=>{
	return (a-b)
})
return res
}

先取出不重复的数，再排序

发表于 2021-06-10 10:20:28 回复(0)

JavaScript

王志晗

function FindNumsAppearOnce( array ) {
    // write code here
    array.sort((a, b) => a - b);
    let map = new Map();
    for(let i = 0; i < array.length; i++){
        if(map.has(array[i])){
            map.set(array[i], map.get(array[i]) + 1);
        }else{
            map.set(array[i], 1);
        }
    }
    let res = [];
    map.forEach((val, key) => {
        if(val === 1){
            res.push(key);
        }
    });
    return res;
}
module.exports = {
    FindNumsAppearOnce : FindNumsAppearOnce
};

发表于 2021-06-09 10:14:47 回复(0)

JavaScript

球球来一个offer吧

用异或^可解此题。

但是首先要知道一个知识点，a^b^a = a^a^b = b^a^a =b，这个知识点也就是本题的简单版本：如果数组中除了某一个数字，其他数字都出现了两次，找出该数字。思路就是遍历数组，对每一个数字都求异或，最后得到的值就是要找的数字。

有了该知识点的储备，再来看看本题。本题是要找两个数字a和b，那我们把该数组分成两个数组，其中a和一部分出现两次的数字在一块儿，b和另一部分出现两次的数字在一块儿，那这两个数组不是就变成了上面讲的那个简单版本中的数组吗？然后再分别对这两个数组求异或，就可以找到这两个数字了。

举例：[a,2,2,3,3,b]。把该数组分成[a,2,2]和[3,3,b]，再对这两个数组求异或，便能得到a和b。

问题：怎么把a和b区分开来？

可以利用二进制来区分。先对整个数组求异或得到c，根据上面的知识，可以知道c其实就是a^b=c。那么对于c，假如c二进制的第一位是1，其实就代表a二进制的第一位是1（或0），b二进制的第一位是0（或1），总而言之如果第一位的c等于1，那么a和b在第一位肯定不相等。

所以我们就可以想到利用二进制的第一位（有可能是第二位，第三位。。。因为上面是假设的c第一位是1）为1来区分两个数组，第一位为1的是数组一，第一位为0的是数组二。这样就相当于把a和b给区分开来了。

a和b区分开以后，剩下的就简单了，判断数组中其他数字的二进制的第一位是否为1，是的话就分到数组一，为0就分到数组二。最后对数组一和数组二分别进行异或，得到的就是a和b。

有个地方没有讲清楚，利用二进制的第一位为1来区分两个数组，如果第一位不是1，那就判断第二位，第三位，一直到找到为1的地方。假设一直找到第n位才为1，那就判断数组中的其他数字的二进制的第n位是否为1，做&运算即可判断。

位运算感觉还是挺抽象的，我也是用具体的例子来照着别人的代码推一遍才搞明白，为什么那个地方做&运算就可以得到它，为什么那个地方做^运算又可以得到它。要是还没看懂的小伙伴也可以自己写一个具体的数组，然后照着代码先在草稿纸上推一遍，多搞几次就明白了。

最后附上js代码

function FindNumsAppearOnce( array ) {
    // write code here
    var res = 0;  //对整个数组求异或的结果
    for(var i = 0; i < array.length; i++){
        res ^= array[i];
    }
    var compare = 1; 
    while((compare & res) == 0){ //判断异或结果的二进制第一位是否为1，为1则直接跳过该循环
        compare <<= 1;         //为0则继续往后找，一直到找到为1的二进制位，该行代码也相当于compare *=2
    }
    var a = 0;
    var b = 0;
    for(var i = 0; i < array.length; i++){  //遍历数组，开始判断数字们的compare位是否为1
        if((compare & array[i]) == 0){     //如果该数字二进制的第某位为0，则分到数组一
            a ^= array[i];                 //对数组一进行异或，得到a
        }else{                             //如果该数字二进制的第某位为1，则分到数组二 
            b ^= array[i];                 //对数组二进行异或，得到b
        }
    }
    return a < b ? [a,b] : [b,a];
}

编辑于 2021-03-30 14:05:22 回复(9)

JavaScript

IPzzzi

function FindNumsAppearOnce( array ) {
    // write code here
    array.sort();
    var result = [];
    var i = 0;
    while(i < array.length){
        if(array.indexOf(array[i]) != array.lastIndexOf(array[i])){
            i = array.lastIndexOf(array[i]) + 1;
        }else{
            result.push(array[i]);
            i++;
        }
    }
    return result;
}

先把初始数组array排序，然后循环判断当前值的第一个索引和最后一个索引的值是不是相等，如果不等，说明出现不止一次，让i跳步，如果相等，说明只出现一次，是我们想要的值

发表于 2021-03-23 17:28:51 回复(2)

提交观点

问题信息

位运算哈希

上传者：牛客301499号

难度：

15条回答 1217收藏 6300浏览

通过挑战的用户

查看代码

wolfleong

2023-02-22 11:49:23
LittleS...

2023-02-20 11:08:57
ralphywj

2022-10-30 15:19:04
牛客89418...

2022-10-27 16:26:43
caixiao

2022-09-26 19:37:31

数组中只出现一次的两个数字

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题