沈阳电力建设总公司网站,可以观看国外短视频的app,网站建设适合的企业,上海手机端建站模板442. 数组中重复的数据
题目
给你一个长度为 n 的整数数组 nums #xff0c;其中 nums 的所有整数都在范围 [1, n] 内#xff0c;且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数#xff0c;并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅…442. 数组中重复的数据
题目
给你一个长度为 n 的整数数组 nums 其中 nums 的所有整数都在范围 [1, n] 内且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。
代码
class Solution {public ListInteger findDuplicates(int[] nums) {ListInteger listnew ArrayList();int nnums.length;for(int i0;in;i){nums[(nums[i]-1)%n]n;}for(int i0;in;i){if(nums[i]2*n)list.add(i1);}return list;}
}思考
和之前做过的找数组中消失的数字思路是类似的 直接用自身数组当成了辅助数组
41. 缺失的第一个正数
题目
给你一个未排序的整数数组 nums 请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
代码
## 排序了时间复杂度不满足O(n)
class Solution {public int firstMissingPositive(int[] nums) {int ans1;Arrays.sort(nums);for(int i0;inums.length;i){if(nums[i]0 nums[i]ans)ans;}return ans;}
}class Solution {public int firstMissingPositive(int[] nums) {int nnums.length;for(int i0;in;i){if(nums[i]0)nums[i]n1;}for(int i0;in;i){int tempMath.abs(nums[i]);if(temp-1n)nums[temp-1]-Math.abs(nums[temp-1]);}for(int i0;in;i){if(nums[i]0)return i1;}return n1;}
}思考
在空间复杂度有限制的情况下那就是要原地哈希或者自身当做自己辅助数组但我就是没有想出来(╥╯^╰╥)。如果上一道题442. 数组中重复的数据我没有偷懒用官解二添负号的标记方法写了也许能想出来吧也许吧。 官解一思路 有个小细节不要重复添加。
485. 最大连续 1 的个数
题目
给定一个二进制数组 nums 计算其中最大连续 1 的个数。
代码
class Solution {public int findMaxConsecutiveOnes(int[] nums) {int max0,n0;for(int i0;inums.length;i){if(nums[i]0){maxnmax? n:max;n0;} elsen;}return maxnmax? n:max;}
}思考
真正的简单题
