力扣打卡day09——缺失的第一个正数、矩阵置零

41. 缺失的第一个正数 - 力扣LeetCode思路/**创建一个标记数组把出现过的正数标记为 1找第一个没标记0的位置返回它对应的数字*/class Solution { public int firstMissingPositive(int[] nums) { /** 创建一个标记数组 把出现过的正数标记为 1 找第一个没标记0的位置 返回它对应的数字 */ int nnums.length; if(n0) return 1; int number[]new int[n]; for(int i0;in;i){ //结果的数据只能在1~n1里面, 大于n 的没必要看了 if(nums[i]0 nums[i]n){ number[nums[i]-1]1;// 把出现过的正数标记为 1 } } //找第一个没标记0的位置 for(int i0;in;i){ if(number[i]0){ return i1; } } //数组都满了结果就是n1 return n1; } }/** 直接暴力解法 **/ class Solution { public int firstMissingPositive(int[] nums) { SetInteger setnew HashSetInteger(); for(int i0;inums.length;i){ set.add(nums[i]); } int i1; while(set.contains(i)){ i; } return i; } }73. 矩阵置零 - 力扣LeetCode思路思路一: 用 O(mn)额外空间两遍扫matrix,第一遍用集合记录哪些行,哪些列有0;第二遍置0class Solution { public void setZeroes(int[][] matrix) { SetInteger row_setnew HashSet(); SetInteger col_setnew HashSet();; int rowmatrix.length; int colmatrix[0].length; for(int i0;irow;i){ for(int j0;jcol;j){ if(matrix[i][j]0){ row_set.add(i); col_set.add(j); } } } //将行列置为0 for(int i0;irow;i){ for(int j0;jcol;j){ if(row_set.contains(i) || col_set.contains(j)){ matrix[i][j]0; } } } } }思路二: 用O(1)空间关键思想: 用matrix第一行和第一列记录该行该列是否有0,作为标志位但是对于第一行,和第一列要设置一个标志位,为了防止自己这一行(一列)也有0的情况.注释写在代码里,直接看代码很好理解!class Solution { public void setZeroes(int[][] matrix) { int row_lenmatrix.length; int col_lenmatrix[0].length; boolean row_flagfalse; boolean col_flagfalse; //记录第一行是否有0 for(int j0;jcol_len;j){ if(matrix[0][j]0){ row_flagtrue; break; } } //记录第一列是否有0 for(int j0;jrow_len;j){ if(matrix[j][0]0){ col_flagtrue; break; } } //进行标志位的计算 for(int i1;irow_len;i){ for(int j1;jcol_len;j){ if(matrix[i][j]0){ matrix[0][j]matrix[i][0]0; } } } //进行放置0 for(int i1;irow_len;i){ for(int j1;jcol_len;j){ if(matrix[i][0]0 || matrix[0][j]0){ matrix[i][j]0; } } } if(row_flag){ for(int j0;jcol_len;j){ matrix[0][j]0; } } if(col_flag){ for(int i0;irow_len;i){ matrix[i][0]0; } } } }