LeetCode hot100-17
41. 缺失的第一个正数给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
这题要求空间复杂度为O(1)，要么定义单个变量，要么原地操作。定义长度为n的数据结构空间复杂度应该是O(n)。我写出来就是空间复杂度O(n)的算法，时间复杂度O(n)。但是能通过… 思路就是用HashSet的contains方法，从1往后看哪个不包含了。
注意，我最开始不是用的set，用的Arrays.asList(newNums).contains(i)，这样会超时，换成set就不会超时了。去看了下这两个contains的时间复杂度。
Arrays.asList(...).contains(...): 这是一个链式调用，Arrays.asList 创建一个固定大小的列表，然后 contains 方法在这个列表上进行线性搜索，时间复杂度为 O(n)。
HashSet.contains 方法的时间复杂度是 O(1)。这意味着在集合中查找元素的时间不会随着集合的大小而增加。在 HashSet 内部，元素是通过计算其哈希码然后存储在基于这个哈希码的位置上的。因此，查找元素时只需要计算该元素的哈希码并查找对应的存储位置即可。如果该位置上有元素且通过 equals 方法比较也匹配，则找到了元素；否则，没有找到元素。
这个特性使得 HashSet.contains 方法能够非常快速地确定元素是否存在于集合中，无论集合中有多少元素。
我的代码
Arrays.stream(nums).boxed().toArray(Integer[]::new);这一句是为了把int类型转为Integer类型，因为Arrays.asList只能用包装类
这个方法接受一个泛型参数 T，表示数组或者参数的类型。T 必须是一个引用类型，不能是一个基本类型，例如 int, double, char 等。如果传入一个基本类型的数组，Arrays.asList() 会把它当作一个 Object 类型的元素，而不是把它的每个元素当作 Object 类型。这样就会导致返回的 List 只有一个元素，就是原始数组本身。
class Solution {public int firstMissingPositive(int[] nums) {Integer[] newNums = Arrays.stream(nums).boxed().toArray(Integer[]::new);Integer i = 1;Set<Integer> set = new HashSet<>(Arrays.asList(newNums));while (set.contains(i)) {i++;}return i;}
}
官方解法
interesting！有一种手动hash的感觉。
1.把<=0的数改为n+1，这一步就是为了出去非正数，因为他们不影响结果。只需要在正数里面找没出现过的。用这个n+1是因为n个数，里面没出现过的正整数最大只能到n+1，用n+1赋值不影响结果。这里用一个正无穷也是一样的效果。
2.遍历数组中的每一个数x, 将x的绝对值-1作为下标，将这个下标对应的数变成负数（已经是负数就不变）。这一步就是就类似于一个大小为n的数组M，数组M中最大的数为y。那就定义一个大小为y的数组N，然后把M数组中的值-1作为下标散列到数组N中去。然后从前往后遍历，没有被散列到的位置+1就是没出现过的最小的数。
3.按照第2步描述的思想遍历找结果
class Solution {public int firstMissingPositive(int[] nums) {int n = nums.length;for (int i = 0; i < n; ++i) {if (nums[i] <= 0) {nums[i] = n + 1;}}for (int i = 0; i < n; ++i) {int num = Math.abs(nums[i]);if (num <= n) {nums[num - 1] = -Math.abs(nums[num - 1]);}}for (int i = 0; i < n; ++i) {if (nums[i] > 0) {return i + 1;}}return n + 1;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/first-missing-positive/solutions/304743/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。