企业前端面试题——企业面试真题22

灰太狼 2022-12-03 01:58 180阅读 0赞

> **找出数组中两个只出现一次的数字**：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(1).要求：给出算法描述，并且给出核心代码

已知:

*  相同的两个数字按位异或, 结果为0
 *  一个数字跟0按位异或, 结果为其本身

思路:

> 根据题目的表述, 有数组如下:  
> \[A1, A2, A3, A4, A5, A6, A7, A8\]  
> 这当中有两个独立数字, 其余均为成对出现, 因此数组长度必然为偶数

**第一步, **我们将A1~A8所有数字, 全部异或在一起, 即:

A1^A2^A3^A4^A5^A6^A7^A8

由于已知条件, 那么相同数字将变成0, 相互抵消

最终, 结果等价于两个独立数字的异或结果.

假设得到的结果为: 0001 0100 (二进制)

var r1 = arr[0]^arr[1];
    for(var i=2; i<arr.length; i++){
        r1 = r1^arr[i]
    }

**第二步**, 由第一步结果可以得知, 两个独立数字, 在bit位的第3位上不同的.

其实第5位也不相同, 但我们只看一个就够了.

那就意味着, 两个独立数字, 分别为

> xxxx x1xx 独立数字 **M**  
> xxxx x0xx 独立数字 **N**

**第三步, **构造出一个***检查数字***, 类似于下面这样:

> 0000 0100 检查数字W

var w = 1;
    while( r1&w != w) {
        w<<1;
    }

**第四步, **找出数组中, 所有第**3**位都等于**1**的数字

检测方法, 就是跟 数字W按位与

若 A&W == 1 , 则表示 数字A的第3位是1

> 找出的所有数字个数, 必定为奇数, 因为这当中包含了相同的数字, 和某一个独立数字 **M**

var M = 0;
    for(var i=0; i<arr.length; i++){
        if(arr[i]&w == 1) M = M^arr[i];
    }

**第五步, **根据第一步的方法, 将找出的这些数字全部异或, 则得出独立数字M

独立数字M已经得到

**第六步,** 数字M与第一步结果进行异或, 则得出独立数字N

var N = M^r1;

## **完整代码** ##

var r1 = arr[0]^arr[1];
    for(var i=2; i<arr.length; i++){
        r1 = r1^arr[i]
    }
    var w = 1;
    while( r1&w != w) {
        w<<1;
    }
    var M = 0;
    for(var i=0; i<arr.length; i++){
        if(arr[i]&w == 1) M = M^arr[i];
    }
    var N = M^r1;
    
    console.log(M, N);

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关企业面试真题：企业面试真题--052

> 选择排序的基本思路是什么? > 第一步:在未排序的序列中找到最大(小)的元素与第1个元素交换; > 第二步:在剩余未排序元素中继续寻找最大(小)的元素与第2个元素交换;

淡淡的烟草味﹌/ 2023年10月06日 15:57/ 0 赞/ 9 阅读

相关企业面试真题——051

试计算100! > 在不考虑越界的情况下,可以使用递归、for循环等方法一： function factorial(num) { if (num

男娘i/ 2023年10月06日 15:54/ 0 赞/ 13 阅读

相关企业面试真题--032

> 实现lodash的 \_.get 方法 var object = { 'a': [{ 'b': { 'c': 3 } }] }; _.get(

偏执的太偏执、/ 2022年12月06日 01:08/ 0 赞/ 138 阅读

相关企业前端面试题——企业面试真题22

> 找出数组中两个只出现一次的数字：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(1).要求：给出算法描述，并

灰太狼/ 2022年12月03日 01:58/ 0 赞/ 181 阅读

相关企业前端面试题——企业面试真题23

给你一个数组 candies 和一个整数 extraCandies ，其中 candies\[i\] 代表第 i 个孩子拥有的糖果数目。对每一个孩子，检查是否存在一种方案，

╰半夏微凉°/ 2022年12月03日 01:57/ 0 赞/ 256 阅读

相关前端面试题：企业面试真题——16

> 小Q是一个专业的射击运动员，有一天他像往常一样进行n次射击训练，每次射击他都会取最高的四次得分作为最终得分来衡量他的射击状态，但是今天他制定了一个奇怪的规则：在n次射击得分

我会带着你远行/ 2022年11月30日 12:38/ 0 赞/ 158 阅读

相关前端面试题：企业面试真题—13

> 用js实现一个随机打乱数组顺序的函数，要求可以设定数组种任意1个元素的位置不变，其他位置的元素位置随机变化。 function shuffle(arr=[], f

Myth丶恋晨/ 2022年11月29日 12:59/ 0 赞/ 158 阅读

相关企业面试真题--008

> 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。 > 你可以假设每种输入只会对应一个答案。但

Myth丶恋晨/ 2022年11月29日 11:54/ 0 赞/ 133 阅读

相关企业面试真题--007

//以下代码迭代太深会造成stack溢出, 改写成不会出错的代码 var queue = ...... var nextItem = function(

今天药忘吃喽~/ 2022年11月29日 05:31/ 0 赞/ 146 阅读

相关 zookeeper 企业面试真题

5.1 请简述 ZooKeeper 的选举机制 [详见][Link 1] 5.2 ZooKeeper 的监听原理是什么？ [详见][Link 1] 5.3 Z

快来打我*/ 2022年11月03日 11:18/ 0 赞/ 150 阅读