41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

1
2

输入：nums = [1,2,0]
输出：3

示例 2：

1
2

输入：nums = [3,4,-1,1]
输出：2

示例 3：

1
2

输入：nums = [7,8,9,11,12]
输出：1

这一题也是我没想到的解法，只知道用哈希，没想到原地哈希，直接操作原数组：

最早知道这个思路是在《剑指 Offer》这本书上看到的，感兴趣的朋友不妨做一下这道问题：剑指 Offer 03. 数组中重复的数字。下面简要叙述：

由于题目要求我们「只能使用常数级别的空间」，而要找的数一定在 [1, N + 1] 左闭右闭（这里 N 是数组的长度）这个区间里。因此，我们可以就把原始的数组当做哈希表来使用。事实上，哈希表其实本身也是一个数组； 我们要找的数就在 [1, N + 1] 里，最后 N + 1 这个元素我们不用找。因为在前面的 N 个元素都找不到的情况下，我们才返回 N + 1； 那么，我们可以采取这样的思路：就把 11 这个数放到下标为 00 的位置， 22 这个数放到下标为 11 的位置，按照这种思路整理一遍数组。然后我们再遍历一次数组，第 11 个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。 这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为 i 的数映射到下标为 i - 1 的位置。

作者：liweiwei1419 链接：https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public static int firstMissingPositive(int[] nums) {

    int n=nums.length;
    for(int i=0;i<n;i++){
        while(nums[i]>0&&nums[i]<=n&&nums[i]!=i+1&&nums[nums[i]-1]!=nums[i]){
            //替代以后还要不断判断这一个数，因为新的数来了,所以用while
            //nums[nums[i]-1]!=nums[i]这个条件必须要用上，不仅可以简化运算，还要针对这种【1，1】无限循环的情况
            swap(nums,i,nums[i]-1);
        }

    }
    for(int i=0;i<n;i++){
        if(nums[i]!=i+1)
            return i+1;
    }
    return n+1;//针对只有【1】的数组
}

相似的一题，剑指offer3：

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

1
2
3

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

这一题给了明示，所有数字都在 0～n-1 的范围内，也是同样的方法,原地hash

可以看作成为一种排序占位，值为i的占到下标为i的位置，如果有人占到位子，说明重复了，最终达到O(n)的时间复杂度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public static int findRepeatNumber(int[] nums) {

    int n=nums.length;
    for(int i=0;i<n;i++){

        while(nums[i]!=i){
            if(nums[i]==nums[nums[i]])  return nums[i];
            swap(nums,i,nums[i]);
        }
    }

    return 1;
}