JS算法之找出缺失的整数

笔记

算法对于一名程序员来说是个硬骨头，很难啃，悲剧的是啃完了还未必有用——除了面试的时候。这不，这次为了要面试，这些天关注各种关于算法的资料，在实际开发中，我也是用的时候才会去用，一般不会涉及到算法。
下面直接上题目吧

题目：一个无序数组里有99个不重复正整数，范围从1到100，唯独缺少一个整数。如何找出这个缺失的整数？

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

此题有多种解法：
1、创建一个HashMap，以1到100为键，值都是0 。然后遍历整个数组，每读到一个整数，就找到HashMap当中对应的键，让其值加一。由于数组中缺少一个整数，最终一定有99个键对应的值等于1, 剩下一个键对应的值等于0。遍历修改后的HashMap，找到这个值为0的键。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 当前的无序数组
var DisorderedArray = [1,2,5,3,6,4,...99] //此处省略
var HashMap = new Array(n);
// 遍历HashMap
for(var i = 0; i < HashMap.length; i++){
    HashMap[i] = 0;
}
// 遍历无序数组
for(var j = 0; j < DisorderedArray.length; j++){
    HashMap[j] += 1;
}
for(var k = 0; k < HashMap.length; k++){
    if(HashMap[k] === 0){
        return k;
        break;
    }
}

以上解法在时间上是最优的，但额外开辟了空间，如何能够降低空间复杂度呢？

此时，便有了解法2：
先把数组元素进行排序，然后遍历数组，检查任意两个相邻元素数值是否是连续的。如果不连续，则中间缺少的整数就是所要寻找的；如果全都连续，则缺少的整数不是1就是100。
假设数组长度是N，如果用时间复杂度为O（NLogN）的排序算法进行排序，那么该解法的时间复杂度是O（NLogN），空间复杂度是O（1）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 当前的无序数组
var DisorderedArray = [1,2,5,3,6,4,...99] //此处省略
DisorderedArray.sort();
for(var i = 1; i < DisorderedArray.length; i++){
    var prev = DisorderedArray[i-1],
        item = DisorderedArray[i];
    if(item - prev != 1){
        return item-1;
        break;
    }else{
        if(DisorderedArray[0] == 2){
            return 1;
            break;
        }
        if(DisorderedArray[n] == (DisorderedArray.length-1)){
            return DisorderedArray.length;
            break;
        }
    }
}

以上解法是没有开辟额外空间的，但是时间复杂度又大了，有办法让时间和空间都进一步优化么？

此时，解法3出现：
很简单也很高效的方法，先算出1+2+3….+100的和，然后依次减去数组里的元素，最后得到的差，就是唯一缺失的整数。
假设数组长度是N，那么该解法的时间复杂度是O（N），空间复杂度是O（1）。

1
2
3
4
5
6
7
8
9
var DisorderedArray = [1,2,5,3,6,4,...99] //此处省略
var res = 0;
for(var i = 1; i < 101; i++){
    res += i;
}
for(var j = 0; j < DisorderedArray.length; j++){
    res -= DisorderedArray[j]
}
// 最后这里的res就是最后缺失的整数

以上解法，对于没有重复元素的数组，这解法在时间和空间上已经是最优了。下面开始扩展问题

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

此扩展的题目来看，用上面的三种方法是没有用的，在这里，就要运用到异或运算，于是就有这了这样的解法：遍历整个数组，依次做异或运算。由于异或在位运算时相同为0，不同为1，因此所有出现偶数次的整数都会相互抵消变成0，只有唯一出现奇数次的整数会被留下。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// js异或运算符(^)
var arr = [4,4,6,8,8,2,3,3,7,6,7,1,5,9,1,5,9];
var res;
for (var i = 0; i < arr.length; i++) {
    var flag = false;
    for (var j = 0; j < arr.length; j++) {
        if(i != j){
            var aaa = arr[i] ^ arr[j];
            if(!aaa) {
                flag = true;
                break;
            }
        }
    }
    if(!flag){
        res = i;
        break;
    }
}
console.log(res)  // 5
console.log(arr[res])  // 2

此处我不得不说一下上面的方法，虽然上面的代码解决了问题，可是还是使用了大题代码，这在性能上还是会有很大的损耗的。于是就有了我下面这段代码，依然可以得到答案，而且大减少了代码量

1
2
3
var arr = [4,4,6,8,8,2,3,3,7,6,7,1,5,9,1,5,9];
arr.reduce((prev,next) => prev ^ next); // 此处得到结果为2
// 由于异或在位运算时相同为0，不同为1，因此所有出现偶数次的整数都会相互抵消变成0，只有唯一出现奇数次的整数会被留下

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

解法：

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

举个例子，如果最终异或的结果是5，转换成二进制是00000101。此时我们可以选择任意一个是1的二进制位来分析，比如末位。把两个奇数次出现的整数命名为A和B，如果末位是1，说明A和B转为二进制的末位不同，必定其中一个整数的末位是1，另一个整数的末位是0。

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

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

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