41. 缺失的第一个正数(数组)
1.题目：
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3
示例 2：
输入：nums = [3,4,-1,1] 输出：2
示例 3：
输入：nums = [7,8,9,11,12] 输出：1
提示：
1 <= nums.length <= 5 * 105-231 <= nums[i] <= 231 - 1
2.思路：
如果本题没有额外的时空复杂度要求，那么就很容易实现：
可以将数组所有的数放入哈希表，随后从 111 开始依次枚举正整数，并判断其是否在哈希表中；
我们可以从 1开始依次枚举正整数，并遍历数组，判断其是否在数组中。
如果数组的长度为 NNN，那么第一种做法的时间复杂度为 O(N)，空间复杂度为 O(N)；第二种做法的时间复杂度为O(N^2)，空间复杂度为 O(1)。但它们都不满足时间复杂度为 O(N) 且空间复杂度为 O(1)。
「真正」满足时间复杂度为 O(N) 且空间复杂度为 O(1)的算法是不存在的，但是我们可以退而求其次：利用给定数组中的空间来存储一些状态。也就是说，如果题目给定的数组是不可修改的，那么就不存在满足时空复杂度要求的算法；但如果我们可以修改给定的数组，那么是存在满足要求的算法的。
方法一：哈希表
第一种做法：
我们可以将数组所有的数放入哈希表，随后从 1开始依次枚举正整数，并判断其是否在哈希表中。仔细想一想，我们为什么要使用哈希表？这是因为哈希表是一个可以支持快速查找的数据结构：给定一个元素，我们可以在 O(1) 的时间查找该元素是否在哈希表中。因此，我们可以考虑将给定的数组设计成哈希表的「替代产品」。
实际上，对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。这是因为如果 [1,N]都出现了，那么答案是 N+1，否则答案是 [1,N]中没有出现的最小正整数。这样一来，我们将所有在 [1,N] 范围内的数放入哈希表，也可以得到最终的答案。而给定的数组恰好长度为 N，有了一种将数组设计成哈希表的思路：
对数组进行遍历，对于遍历到的数 x，如果它在 [1,N]的范围内，那么就将数组中的第 x−1个位置（注意：数组下标从 0开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。
那么如何设计这个「标记」呢？由于数组中的数没有任何限制，因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质：由于我们只在意 [1,N]中的数，因此我们可以先对数组进行遍历，把不在 [1,N]范围内的数修改成任意一个大于 N的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。算法的流程如下：
我们将数组中所有小于等于 0 的数修改为 N+1；
我们遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 ∣x∣，如果 ∣x∣∈[1,N]，那么我们给数组中的第 ∣x∣−1个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；
在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加 1。
3.代码：
class Solution {
public int firstMissingPositive(int[] nums) {
//将数字中小于等于0的数改为 N+1
for(int i=0;i<nums.length;i++){
if(nums[i]<=0){
nums[i]=nums.length+1;
}
}
//遍历数组中的每一个数，它可能已经被打了标记，因此绝对值
//如果在长度范围内，那给数组中的第 ∣x∣−1个位置的数添加一个负号
for(int i=0;i<nums.length;i++){
int num=Math.abs(nums[i]);
if(num<=nums.length){
nums[num-1]=-Math.abs(nums[num-1]);
}
}
//遍历完成后如果其中每一个数都是负数，那么答案是n+1，否则答案是第一个正数位置加1.
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
return i+1;
}
}
return nums.length+1;
}73. 矩阵置零
1.题目：
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示：
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrix[i][j] <= 231 - 1
2.思路：
//用两个标记数组记录是否有0出现，出现了将标记数组改为true,再遍历一遍寻找标记的位置文章来源：https://www.toymoban.com/news/detail-662056.html
//将原数组位置被标记的元素替换为0；文章来源地址https://www.toymoban.com/news/detail-662056.html
3.代码：
class Solution {
public void setZeroes(int[][] matrix) {
//用两个标记数组记录是否有0出现，出现了将标记数组改为true,再遍历一遍寻找标记的位置
//将原数组位置被标记的元素替换为0；
int m=matrix.length,n=matrix[0].length;
boolean[] row=new boolean[m];
boolean[] col=new boolean[n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]==0){
row[i]=true;
col[j]=true;
}
}
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(row[i]||col[j]){
matrix[i][j]=0;
}
}
}
}
}到了这里，关于Practices11|41. 缺失的第一个正数(数组)、73. 矩阵置零（矩阵）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
