用火车采集器发布信息时 如何获取网站栏目id,wap浏览器模拟,广州微网站建设怎么样,wordpress5.2 注册验证41. 缺失的第一个正数(数组)
1.题目#xff1a;
给你一个未排序的整数数组 nums #xff0c;请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1#xff1a;
输入#xff1a;nums [1,2,0]
输出#xf…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,N1] 中。这是因为如果 [1,N]都出现了那么答案是 N1否则答案是 [1,N]中没有出现的最小正整数。这样一来我们将所有在 [1,N] 范围内的数放入哈希表也可以得到最终的答案。而给定的数组恰好长度为 N有了一种将数组设计成哈希表的思路
对数组进行遍历对于遍历到的数 x如果它在 [1,N]的范围内那么就将数组中的第 x−1个位置注意数组下标从 0开始打上「标记」。在遍历结束之后如果所有的位置都被打上了标记那么答案是 N1否则答案是最小的没有打上标记的位置加 1。
那么如何设计这个「标记」呢由于数组中的数没有任何限制因此这并不是一件容易的事情。但我们可以继续利用上面的提到的性质由于我们只在意 [1,N]中的数因此我们可以先对数组进行遍历把不在 [1,N]范围内的数修改成任意一个大于 N的数例如 N1。这样一来数组中的所有数就都是正数了因此我们就可以将「标记」表示为「负号」。算法的流程如下
我们将数组中所有小于等于 0 的数修改为 N1
我们遍历数组中的每一个数 x它可能已经被打了标记因此原本对应的数为 ∣x∣如果 ∣x∣∈[1,N]那么我们给数组中的第 ∣x∣−1个位置的数添加一个负号。注意如果它已经有负号不需要重复添加
在遍历完成之后如果数组中的每一个数都是负数那么答案是 N1否则答案是第一个正数的位置加 1。
3.代码
class Solution {public int firstMissingPositive(int[] nums) {//将数字中小于等于0的数改为 N1for(int i0;inums.length;i){if(nums[i]0){nums[i]nums.length1;}}//遍历数组中的每一个数它可能已经被打了标记因此绝对值//如果在长度范围内那给数组中的第 ∣x∣−1个位置的数添加一个负号for(int i0;inums.length;i){int numMath.abs(nums[i]);if(numnums.length){nums[num-1]-Math.abs(nums[num-1]);}}//遍历完成后如果其中每一个数都是负数那么答案是n1否则答案是第一个正数位置加1.for(int i0;inums.length;i){if(nums[i]0){return i1;}}return nums.length1;}
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,再遍历一遍寻找标记的位置 //将原数组位置被标记的元素替换为0
3.代码
class Solution {public void setZeroes(int[][] matrix) {//用两个标记数组记录是否有0出现出现了将标记数组改为true,再遍历一遍寻找标记的位置//将原数组位置被标记的元素替换为0int mmatrix.length,nmatrix[0].length;boolean[] rownew boolean[m];boolean[] colnew boolean[n];for(int i0;im;i){for(int j0;jn;j){if(matrix[i][j]0){row[i]true;col[j]true;}}}for(int i0;im;i){for(int j0;jn;j){if(row[i]||col[j]){matrix[i][j]0;}}}}
}
