题意分析

  • 首先，这个题目的题目描述有点问题。而且测试数据估计比较水。希望可以加强一下。
  • 其实，我们来说一下这个题目的大意。就是给你一个数组，需要你快速找出这个数组里面没有出现过的最小的正整数。怎么快速呢？就是要做到O(n),然后呢？就是，空间复杂度要控制在O(1).

思路分析

解法一 哈希

  • 这种想法是对出现过的数字进行哈希，然后我们发现，这个数组一共就n个数字，那么最小没有出现过的正整数也不会超过n+1.所以其实O(n)的时间复杂度是很好实现的。所以，我们先进行哈希，然后从1-n+1遍历一遍，返回第一个没有出现过的数字即可。
  • 代码如下
    • 需要从1-n遍历一遍，时间复杂度为O(n)
    • 但是，这里我们用了哈希，很显然空间复杂度为O(n)，这是不符合题目要求的，但是也能过。所以数据很弱。 
class Solution {
public:
    /**
     * return the min number
     * @param arr int整型vector the array
     * @return int整型
     */
    int minNumberdisappered(vector<int>& arr) {
        // write code here
        unordered_map<int,bool> mp;
        // 先对出现过的数进行标记
        for(auto x:arr){
            mp[x]=true;
        }
        int n=arr.size();
        // 直接找1-n之间的数就行了
        for(int i=1;i<=n;i++){
            if(!mp[i]){
                return i;
            }
        }
        // 如果循环结束后都没有退出，那么说明1-n之间的数字都有，直接返回n+1
        return n+1;
    }
};

解法二 位运算

  • 一般来说，如果题目要求空间复杂度为O(1)的算法，很大程度上需要使用位运算进行求解。对于这个题目，我想到了两种位运算的方法。

    • 一种是将所有的n个数字用一个数字表示出来，首先，我们最后的答案一定是在1-n+1里面的，所以，这里我想的是用一个整型表示当前给出的数组的数字情况，比如，出现了1就把第一位表示为1，否则表示为1，出现了2就把第二位表示为1，否则表示为0.依次进行类推。但是我们发现题目给出的n的数据范围很大。一般的整数似乎表示不了，所以这种想法直接咕咕咕了。

    • 接下来，第二种想法是利用的这个题目的给的数据的漏洞。看了大部分题解之后，发现这个题目给出的数据一定是正数部分是连续的或者中间只断了一次。那么也就是题目一定存在1-x(x>0)中的数据或者最多少了一个数字。这样的话我们就可以利用异或运算进行求解了。

图片说明

  • 根据上面的图，我们可以利用异或的第三条性质，我们先把所有出现的正整数异或进一个sum里面，然后从1-n进行遍历，如果这个数字出现过，那么这个异或下来一定是0。最后如果sum为0，说明1-n之间的数字都出现过。返回n+1,否则，sum就是那个未在初始数组里面的最小正整数。

  • 代码如下

    • 需要从1-n进行遍历，时间复杂度为O(n)
    • 仅仅用了几个变量进行处理，空间复杂度为O(1) 
class Solution {
public:
    /**
     * return the min number
     * @param arr int整型vector the array
     * @return int整型
     */
    int minNumberdisappered(vector<int>& arr) {
        // write code here
        // num初始为0，用来表示存储数组里面出现的正整数
        int num=0;
        for(auto x:arr){
            // 如果这个元素大于0，则暂时存入num
            if(x>0) num^=x;
        }
        int n=arr.size();
        for(int i=1;i<=n;i++){
            // 如果这个i出现过，那么异或之后这个对num的贡献就是0
            num^=i;
        }
        // 如果最后num为0，说明1-n都存在，返回n+1,否则返回num即可
        return num==0?n+1:num;
    }
};