LintCode 196 - Find the Missing Number I

Related:
Lintcode 570 - Find the Missing Number II
LeetCode 41 - First Missing Positive
LintCode 196 - Find the Missing Number I
LeetCode 287 - Find the Duplicate Number - Google Interview
http://blog.hyoung.me/cn/2017/02/find-the-missing-number/
Find the Missing Number (LintCode 196)
https://zhengyang2015.gitbooks.io/lintcode/find_the_missing_number_196.html

Given an array contains N numbers of 0 .. N, find which number doesn't exist in the array.

Example

Given N = 3 and the array [0, 1, 3], return 2.

Challenge

Do it in-place with O(1) extra memory and O(n) time.

这道题和first missing positive number思想一样。

遍历数组，看当前位置上的数和其下标是否一致，若不一致，则将该数和正确下标位置上的数交换，然后继续检查新来的数，直到满足条件为止。

最后重新遍历数组，找到第一个下标和数不一致的下标返回即可。若全部满足，则返回下标最大值＋1，即数组长度。

    public int findMissing(int[] nums) {
        // write your code here
        //和first missing positive number思想一样。遍历数组，看当前位置上的数和其下标是否一致，若不一致，则将该数和正确下标位置上的数交换，然后继续检查新来的数，直到满足条件为止。
        if(nums == null || nums.length == 0){
            return 0;
        }

        for(int i = 0; i < nums.length; i++){
            while(nums[i] != i && nums[i] < nums.length){
                //index为num[i]因该被放到的位置
                int index = nums[i];
                //若要放到的位置上已经有正确的数则不交换
                if(nums[index] == nums[i]){
                    break;
                }
                int temp = nums[i];
                nums[i] = nums[index];
                nums[index] = temp;
            }
        }

        for(int i = 0; i < nums.length; i++){
            if(nums[i] != i){
                return i;
            }
        }

        return nums.length;
    }

看到这个题目，最直接的想法往往就是新建一个包含所有数字的集合，然后遍历这个数组，依次把出现过的数从集合中删去，最后集合中剩下的那个数就是没有出现的那个了。这里的时间复杂度是$O\left(N\right)$，空间复杂度也是$O\left(N\right)$，看上去已经很好了。不过如果是这样解的话，未免太过简单了。考虑到无论如何我们都要遍历一遍数组，所以时间复杂度已经是最优了，那么我们能不能优化一下空间复杂度呢？

答案是肯定的。考虑到这里的数据基本上是连续的正整数，那么我们就可以利用桶排序的思想：遍历数组，把每一个数都送到它应该去的地方。

int findMissing(vector<int> &nums) {

int N = nums.size();



int missing = N;

for (int i = 0; i < N; ++i) {

while (nums[i] != i) {

if (nums[i] == N) {

missing = i;

break;

}

swap(nums[i], nums[nums[i]]);

}

}



return missing;

}

外层循环用于确保每个数都待在它应该在的位置，即nums[i] == i，而内层循环用于把属于这个位置的数给「换」回来。这里有一个特殊情况，那就是数N，它很显然无法被放进数组，于是我们就把它当做缺失数的初始值，并且当在数组中碰到它时，我们就把它作为一个「锚」不去主动移动它。每次当我们在某个位置发现它时，那个位置应该存在的数就有可能是缺失数。到最后遍历结束时，要么$N$未曾出现，要么$N$所在位置对应的那个数就是缺失数。

虽然这里有两层循环，但我们很容易就能想到，每一次交换我们都可以保证把一个数移到了它应该在的位置，而最多只需交换$N$次就可以了，因此时间复杂度依然是$O\left(N\right)$，而空间复杂度降到了$O\left(1\right)$。

题解2 - 桶排序

非常简单直观的想法——排序后检查缺失元素，但是此题中要求时间复杂度为 O(n)O(n)O(n), 因此如果一定要用排序来做，那一定是使用非比较排序如桶排序或者计数排序。题中另一提示则是要求只使用 O(1)O(1)O(1) 的额外空间，那么这就是在提示我们应该使用原地交换。根据题意，元素应无重复，可考虑使用桶排，索引和值一一对应即可。第一重 for 循环遍历原数组，内循环使用 while, 调整索引处对应的值，直至相等或者索引越界为止，for 循环结束时桶排结束。最后再遍历一次数组找出缺失元素。

初次接触这种题还是比较难想到使用桶排这种思想的，尤其是利用索引和值一一对应这一特性找出缺失元素，另外此题在实际实现时不容易做到 bug-free, while 循环处容易出现死循环。

难点一在于正确实现桶排，难点二在于数组元素中最大值 N 如何处理。N 有三种可能：

1. N 不在原数组中，故最后应该返回 N
2. N 在原数组中，但不在数组中的最后一个元素
3. N 在原数组中且在数组最后一个元素

其中情况1在遍历桶排后的数组时无返回，最后返回 N.

其中2和3在 while 循环处均会遇到 break 跳出，即当前这个索引所对应的值要么最后还是 N，要么就是和索引相同的值。如果最后还是 N, 也就意味着原数组中缺失的是其他值，如果最后被覆盖掉，那么桶排后的数组不会出现 N, 且缺失的一定是 N 之前的数。

综上，这里的实现无论 N 出现在哪个索引都能正确返回缺失值。实现上还是比较巧妙的，所以说在没做过这类题时要在短时间内 bug-free 比较难，当然也可能是我比较菜...

另外一个难点在于如何保证或者证明 while 一定不会出现死循环，可以这么理解，如果 while 条件不成立且未出现nums.length这个元素，那么就一定会使得一个元素正确入桶，又因为没有重复元素出现，故一定不会出现死循环。

    public int findMissing(int[] nums) {
        if (nums == null || nums.length == 0) return -1;

        bucketSort(nums);
        // find missing number
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }

        return nums.length;
    }

    private void bucketSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                // ignore nums[i] == nums.length
                if (nums[i] == nums.length) {
                    break;
                }
                int nextNum = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = nextNum;
            }
        }
    }

https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/73113

题解1 - 位运算

和找单数的题类似，这里我们不妨试试位运算中异或的思路。最开始自己想到的是利用相邻项异或结果看是否会有惊喜，然而发现 a^(a+1) != a^a + a^1 之后眼泪掉下来... 如果按照找单数的做法，首先对数组所有元素异或，得到数x1, 现在的问题是如何利用x1得到缺失的数，由于找单数中其他数都是成对出现的，故最后的结果即是单数，这里每个数都是单数，怎么办呢？我们现在再来分析下如果没有缺失数的话会是怎样呢？假设所有元素异或得到数x2, 数x1和x2有什么差异呢？假设缺失的数是x0，那么容易知道x2 = x1 ^ x0, 相当于现在已知x1和x2，要求x0. 根据 Bit Manipulation 中总结的交换律，x0 = x1 ^ x2.

位运算的题往往比较灵活，需要好好利用常用等式变换。

    public int findMissing(int[] nums) {
        int x = 0;
        for (int i = 0; i <= nums.length; i++) {
            x ^= i;
        }
        for (int i = 0; i < nums.length; i++) {
            x ^= nums[i];
        }
        return x;
    }

https://zyfu0408.gitbooks.io/interview-preparation/content/bit-manipulation/xor.html
找唯一missing的那个数字，拿数值和index做xor

    public int missingNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result ^= i;
            result ^= nums[i];
        }
        result ^= nums.length;
        return result;
    }

https://segmentfault.com/a/1190000004614168

2. 求和相减法

    public int findMissing(int[] A) {
        int len = A.length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += A[i];
        }
        int targetsum = len * (len + 1) / 2; //0, 1, 2,...,len, 共len+1个数，多加了一个len
        return targetsum - sum;
    }

第二种方法是，只要先按顺序排列好[0, 1, 2, 3, 4, ...]，用二分法找到第一个和A[i]不相等的数i就可以了。

    public int findMissing(int[] A) {
        int len = A.length;
        Arrays.sort(A);
        int left = 0, right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] > mid) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return A[left] == left ? left + 1 : left;
    }

http://www.code123.cc/docs/leetcode-notes/integer_array/first_missing_positive.html

Given an unsorted integer array, find the first missing positive integer.

Example
Given [1,2,0] return 3, and [3,4,-1,1] return 2.

Challenge
Your algorithm should run in O(n) time and uses constant space.

容易想到的方案是先排序，然后遍历求得缺的最小整数。排序算法中常用的基于比较的方法时间复杂度的理论下界为 O(nlogn), 不符题目要求。常见的能达到线性时间复杂度的排序算法有 基数排序，计数排序 和 桶排序。

基数排序显然不太适合这道题，计数排序对元素落在一定区间且重复值较多的情况十分有效，且需要额外的 O(n) 空间，对这道题不太合适。最后就只剩下桶排序了，桶排序通常需要按照一定规则将值放入桶中，一般需要额外的 O(n) 空间，咋看一下似乎不太适合在这道题中使用，但是若能设定一定的规则原地交换原数组的值呢？这道题的难点就在于这种规则的设定。

设想我们对给定数组使用桶排序的思想排序，第一个桶放1，第二个桶放2，如果找不到相应的数，则相应的桶的值不变(可能为负值，也可能为其他值)。

那么怎么才能做到原地排序呢？即若 A[i]=x, 则将 x 放到它该去的地方 - A[x−1]=x, 同时将原来 A[x−1] 地方的值交换给 A[i].

排好序后遍历桶，如果不满足 f[i]=i+1, 那么警察叔叔就是它了！如果都满足条件怎么办？那就返回给定数组大小再加1呗。

http://www.jiuzhang.com/solutions/first-missing-positive/

    public int firstMissingPositive(int[] A) {
        if (A == null) {
            return 1;
        }

        for (int i = 0; i < A.length; i++) {
            while (A[i] > 0 && A[i] <= A.length && A[i] != (i+1)) {
                int tmp = A[A[i]-1];
                if (tmp == A[i]) {
                    break;
                }
                A[A[i]-1] = A[i];
                A[i] = tmp;
            }
        }

        for (int i = 0; i < A.length; i ++) {
                if (A[i] != i + 1) {
                    return i + 1;
                }
        }

        return A.length + 1;
    }

http://blog.hyoung.me/cn/2017/02/find-the-missing-number/

其实这道题目才算是第一题的 follow-up。最主要的区别就在于数组内数性质的变化，不再保证是基本连续的正整数了，其中可能会有负数和重复出现的数。但是利用桶排序的思路并没有变化，只是我们在做交换时需要更多的检查而已。类似于第一题中我们移动在数组中有位置的数，把$N$当做一个「锚」，在这里，我们把所有的负数、重复出现的数，以及在数组范围之外的数当做「锚」。

int firstMissingPositive(vector<int> &A) {


int N = A.size();



for (int i = 0; i < N; ++i) {

while (A[i] > 0 && A[i] <= N && A[i] - 1 != i && A[i] != A[A[i] - 1])

swap(A[i], A[A[i] - 1]);

}



for (int i = 0; i < N; ++i)

if (A[i] != i + 1)

return i + 1;



return N + 1;

}

在这里，我们做了一点小处理，那就是把所有正整数在数组的位置都提前一位了，比如把5放在A[4]，这样可以让整体的逻辑更清晰一点儿，减少出错的机会。

此外，最容易出错的地方就是没有考虑重复数字出现的可能了。如果没有考虑到这一点，内层循环就会陷入到一个死循环当中。这一点也很好想，假设有一个数出现了两次，其中一个正好在它对应的位置上，当遍历到另外一个时，由于肯定与当前位置不符，就需要交换，而换回来的数就是还是它，这就导致了死循环。

桶排序还是一个比较小众的技巧，在这里也算是最大程度地彰显了它的独特之处。不过除此之外，其他的应用就并不那么常见了。