442. 数组中重复的数据|||41. 缺失的第一个正数|||485. 最大连续 1 的个数

442. 数组中重复的数据

题目

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

代码

class Solution {public List<Integer> findDuplicates(int[] nums) {List<Integer> list=new ArrayList<>();int n=nums.length;for(int i=0;i<n;i++){nums[(nums[i]-1)%n]+=n;}for(int i=0;i<n;i++){if(nums[i]>2*n)list.add(i+1);}return list;}
}

思考

和之前做过的找数组中消失的数字，思路是类似的
直接用自身数组当成了辅助数组

41. 缺失的第一个正数

题目

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

代码

## 排序了，时间复杂度不满足O(n)
class Solution {public int firstMissingPositive(int[] nums) {int ans=1;Arrays.sort(nums);for(int i=0;i<nums.length;i++){if(nums[i]>0 && nums[i]==ans)ans++;}return ans;}
}class Solution {public int firstMissingPositive(int[] nums) {int n=nums.length;for(int i=0;i<n;i++){if(nums[i]<=0)nums[i]=n+1;}for(int i=0;i<n;i++){int temp=Math.abs(nums[i]);if(temp-1<n)nums[temp-1]=-Math.abs(nums[temp-1]);}for(int i=0;i<n;i++){if(nums[i]>0)return i+1;}return n+1;}
}

思考

在空间复杂度有限制的情况下，那就是要原地哈希，或者自身当做自己辅助数组，但我就是没有想出来(╥╯^╰╥)。如果上一道题442. 数组中重复的数据我没有偷懒，用官解二，添负号的标记方法写了，也许能想出来吧，也许吧。
官解一思路：

有个小细节，不要重复添加。

485. 最大连续 1 的个数

题目

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

代码

class Solution {public int findMaxConsecutiveOnes(int[] nums) {int max=0,n=0;for(int i=0;i<nums.length;i++){if(nums[i]==0){max=n>max? n:max;n=0;}        elsen++;}return max=n>max? n:max;}
}

思考

真正的简单题！