数组中只出现一次的数（其它数出现k次）

[编程题]数组中只出现一次的数（其它数出现k次）

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

给定一个长度为 n 的整型数组 arr 和一个整数 k(k>1) 。

已知 arr 中只有 1 个数出现一次，其他的数都出现 k 次。

请返回只出现了 1 次的数。

数据范围: $1 \le n \le 2*10^5$ ， $1 \lt k \lt 100$ ， $-2*10^9 \le arr[i] \le 2*10^9$

进阶：时间复杂度 $O(32n)$ ，空间复杂度 $O(1)$

示例1

输入

[5,4,1,1,5,1,5],3

输出

示例2

输入

[2,2,1],2

输出

算法知识视频讲解

Javascript

美英

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

发表于 2021-11-14 16:57:46 回复(1)

Javascript

飞牛cz

发表于 2021-10-10 20:16:58 回复(0)

JavaScript

别卷啦！

遍历数组里面的数的每个比特位，然后将32位比特位中不能被k整除的1，依次还原，最终得到所需数字。

function foundOnceNumber( arr ,  k ) {
    // write code here
   //计算每一位上出现1的个数，%k得到出现一次的数
    let res = 0;
    for(let i=0;i<32;++i){
        let sum =0;
        for(let num of arr){
            //用无符号右移，防止正负号的影响
            //依次右移num，同1相与，计算每一位上1的个数
            sum+=(num>>i)&1
        }
        //对sum取余，左移恢复
        res^=(sum%k)<<i
    }
    return res
}

编辑于 2021-01-15 16:38:43 回复(4)