算法——找出缺失的整数

一、前言

最近智商持续掉线，隐约有种提前犯了阿兹海默症的感觉，偶像剧看多了就是容易智商持续掉线，前一整子关注了个算法的公众号，今天也终于捡着一篇能看懂的了，感觉非常的涨姿势，整篇看下来觉得自己有了很大的提升，仿佛就差一点就看懂了。

以下是原文的链接，为了防止链接被破坏，为了维护涨过的姿势还找得到的和平，阿婆，可爱又迷人的反派角色这里决定开个随笔整理一下文章内容和评论里面的代码，等。

原文请戳这里 http://blog.jobbole.com/106521/

二、请看正文

第一题：请听题，要把大象关冰箱一个无序数组里有99个不重复正整数，范围从1到100，唯独缺少一个整数。如何找出这个缺失的整数？

解法一：

创建一个HashMap，以1到100为键，值都是0 。然后遍历整个数组，每读到一个整数，就找到HashMap当中对应的键，让其值加一。阿婆止步于这一步，因为阿婆就会用JavaScript，所以阿婆打算新建个数组来着

由于数组中缺少一个整数，最终一定有99个键对应的值等于1, 剩下一个键对应的值等于0。遍历修改后的HashMap，找到这个值为0的键。

假设数组长度是N，那么该解法的时间复杂度是O（2N），空间复杂度是O（N）。空间复杂度和时间复杂度这个是阿婆无脑照抄，阿婆打算有时间跪下来百度

分析：

这个解法在时间上是最优的，但是额外开辟了空间。请思考如何去降低空间复杂度？

解法二：

先把数组元素进行排序，然后遍历数组，检查任意两个相邻元素数值是否是连续的。如果不连续，则中间缺少的整数就是所要寻找的；如果全都连续，则缺少的整数不是1就是100。这个阿婆觉得搞起来太复杂，主要是阿婆不打算想破头去排序，果断晃弃掉了

假设数组长度是N，如果用时间复杂度为O（N*LogN）的排序算法进行排序，那么该解法的时间复杂度是O（N*LogN），空间复杂度是O（1）。

分析：

这种解法没有开辟额外空间，但是时间复杂度又大了。请思考有没有办让放时间和空间都优化？

解法三：

很简单也很高效的方法，先算出1+2+3….+100的和，然后依次减去数组里的元素，最后得到的差，就是唯一缺失的整数。看到这里阿婆仿佛觉得很熟悉，仿佛这个题以前从哪里看过，这个解法仿佛还被阿婆深深怀疑过

假设数组长度是N，那么该解法的时间复杂度是O（N），空间复杂度是O（1）。

分析：

对于没有重复元素的数组，这个解法在时间和空间上面是最优的了。下面请思考题目扩展...

第二题： 请听题，一个无序数组里有若干个正整数，范围从1到100，其中99个整数都出现了偶数次，只有一个整数出现了奇数次（比如1,1,2,2,3,3,4,5,5），如何找到这个出现奇数次的整数？

提示: 使用异或运算，在运算时相同结果为0，不同结果为1。

解法：

遍历整个数组，依次做异或运算。由于异或在位运算时相同为0，不同为1，因此所有出现偶数次的整数都会相互抵消变成0，只有唯一出现奇数次的整数会被留下。

假设数组长度是N，那么该解法的时间复杂度是O（N），空间复杂度是O（1）。

第三题： 一个无序数组里有若干个正整数，范围从1到100，其中98个整数都出现了偶数次，只有两个整数出现了奇数次（比如1,1,2,2,3,4,5,5），如何找到这个出现奇数次的整数？

提示: 使用分治法(容阿婆跪去百度)，把数组分成两部分就可以回归到上面的情况了。

解法：

遍历整个数组，依次做异或运算。由于数组存在两个出现奇数次的整数，所以最终异或的结果，等同于这两个整数的异或结果。这个结果中，至少会有一个二进制位是1（如果都是0，说明两个数相等，和题目不符）。

举个例子，如果最终异或的结果是5，转换成二进制是00000101。此时我们可以选择任意一个是1的二进制位来分析，比如末位。把两个奇数次出现的整数命名为A和B，如果末位是1，说明A和B转为二进制的末位不同，必定其中一个整数的末位是1，另一个整数的末位是0。阿婆当时奶脑子都想炸了也没想出来如果为1的不是最后一位怎么办，评论区大大的代码雕雕的表示可以人工闹到最后一位(这个后面的代码里没有体现)

根据这个结论，我们可以把原数组按照二进制的末位不同，分成两部分，一部分的末位是1，一部分的末位是0。由于A和B的末位不同，所以A在其中一部分，B在其中一部分，绝不会出现A和B在同一部分，另一部分没有的情况。

这样一来就简单了，我们的问题又回归到了上一题的情况，按照原先的异或解法，从每一部分中找出唯一的奇数次整数即可。

假设数组长度是N，那么该解法的时间复杂度是O（N）。把数组分成两部分，并不需要借助额外存储空间，完全可以在按二进制位分组的同时来做异或运算，所以空间复杂度仍然是O（1）。

三、评论区代码整理

阿婆将评论区一位叫玻璃猫的大大的代码做了一些处理(用js无脑照抄了一遍)整理出以下代码：

<script>
    //求数组内所有数的异或运算值
    function findoutMissingDigits(arr){
        var result = 0;
        for (var i in arr){
            result ^= arr[i];
        }
        return result;
    }


    //这个方法的返回值用来区分两个数，参数num是两个数的异或运算值
    function getShedNum(num){
        var numShift = 1;

        /**
         * 这个while用来判断num从右往左数哪一位出现了1：
         * 假如num的值是 10 = parseInt('1010',2),numShift的值是 1 = parseInt('0001'，2)
         * 执行numShift = numShift<<1; 将numShift左位移一位得到 2 = numShift = parseInt('0010',2)
         * 直到& 结果不为零得到使两个数异或运算结果不为1的那个数，两个数分别&numShift 得到的结果是0或1
        */
        while((num & numShift) ==0){
            numShift = numShift<<1;
        }

        return numShift;
    }

    function findoutMissingDigits2(arr){
        var A = 0;
        var B = 0;
        var result = findoutMissingDigits(arr);
        //从两个数的异或结果，获得数组分治的“分水岭”
        var shedNum = getShedNum(result);//tips:到这以后如果想用右位移吧1和0放到最后一位的话就计算shedNum转成字符串的字符串长度，右移长度-1位
        for (var i in arr){
            A = ((arr[i] & shedNum) == 0)? (A^arr[i]):A;
            B = ((arr[i] & shedNum) != 0)? (B^arr[i]):B;
        }
        return [A, B];
    }

    findoutMissingDigits2([1,1,2,2,3,3,4,5,6,6,7,7])//[4,5]
</script>

三、总结

以下是阿婆翻阅的大量资料和使用到的姿势点的整理，阿婆脑子都要烧掉惹，智硬~

位运算及其应用详解

十进制转换成二进制：(假设把63转换成2进制)parseInt(63).toString(2);

二进制转换成十进制：(假设把 101110100 转换成10进制) parseInt( "101110100",2);

异或运算 ^： ( parseInt( "1011",2) ^ parseInt( "110",2) ) == parseInt( "1101",2) //true

右位移 >>： ( parseInt( "1011",2) >> 1 ) == parseInt( "101",2) //true ( parseInt( "1011",2) >> 2 ) == parseInt( "10",2) //true

好了，接下来是声明，如果有大大亿一看到了这篇文，看到我引用了你萌的东西没有注明出处，产生了什么不适感，请联系我，另外，无脑照抄的我如果哪里抄的不大对亿一被大大看到的话，请教(一声)我or2