LeetCode解题思路9（Hot100）

解题思路： 遍历并调整数组： 对于每个元素 nums[i]，若其值为正且不超过数组长度 len，则将其逐步交换到它应该在的位置。查找缺失的正整数： 遍历调整后的数组，若某个位置的值不等于其索引加1，则说明 i+1 是最小的缺失正整数。若所有位置均满足 nums[i] = i+1，则说明数组包含1到 len 的所有正整数，此时最小缺失值为 len+1。 Java代码： public class Solution { public int firstMissingPositive(int[] nums) { int len = nums.length; for (int i = 0; i < len; i++) { while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) { swap(nums, nums[i] - 1, i); } } for (int i = 0; i < len; i++) { if (nums[i] != i + 1) { return i + 1; } } return len + 1; } private void swap(int[] nums, int index1, int index2) { int temp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = temp; } } 复杂度分析： 时间复杂度： O(n)，外层循环遍历数组一次，时间为O(n)。空间复杂度： O(1)，仅使用了常数级别的额外空间。

解题思路： 标记阶段： 使用两个布尔数组row和col分别记录哪些行和列包含零元素。 遍历整个矩阵，当遇到零元素matrix[i][j]时，将row[i]和col[j]标记为true。​置零阶段： 再次遍历矩阵，若当前行i或列j被标记为需要置零（即row[i] || col[j]），则将matrix[i][j]设为0。 Java代码： class Solution { public void setZeroes(int[][] matrix) { 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] = 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; } } } } } 复杂度分析： 时间复杂度： O(mn)，其中 m 和 n 分别是矩阵的行数和列数。空间复杂度： O(m+n)，使用两个布尔数组row和col分别记录行和列的标记信息，额外空间与矩阵的行数和列数相关。