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

灰太狼 2022-12-03 01:58 227阅读 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 条评论，227人围观）

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

相关阅读

相关企业前端面试题：企业面试真题--055

> 给定整数n和m,写一个dispatch,把1~n尽量平均地分成m个组. 示例： var n = 2; var m = 2; dispatch(n

朴灿烈づ我的快乐病毒、/ 2023年10月06日 15:59/ 0 赞/ 24 阅读

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

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

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

相关企业面试真题——051

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

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

相关企业面试真题--032

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

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

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

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

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

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

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

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

相关企业面试真题--008

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

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

相关企业面试真题--007

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

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

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

var a = {n:1} var b = a a.x = a = {n:2} console.log(a.x) conso

小灰灰/ 2022年11月28日 13:59/ 0 赞/ 187 阅读

相关 zookeeper 企业面试真题

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

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