>[success] # 数组中重复的数据
* 题目描述
给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
* 要求
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-all-duplicates-in-an-array
>[danger] ##### 第一次解题思路
第一次解题时候想到使用`Map` 结构来进行计算保存出现的次数，虽然解题出来了但是不满足题中要求的空间复杂度`O(1)` ,看了一些大佬使用先排序然后相同数字相同取出的办法排序的时间复杂度是 `O(N∗log(N))`不符合题目的时间复杂度`(N)`
* 第一次 js 解题代码
~~~
/**
* @param {number[]} nums
* @return {number[]}
*/
var findDuplicates = function(nums) {
const countMap = {}
return nums.reduce((acc,cur)=>{
if(!countMap[cur]) countMap[cur] = 0
++countMap[cur]
// 出现两次
if(countMap[cur]===2){
acc.push(cur)
}
return acc
},[])
};
~~~
>[info] ## 题解
在空间想符合`O(1)` 那需要`原地去修改数组`，题目中说数组中的数字不会大于数组的长度，因此数组中`每项减一`都会在当前数组中找到`对应项`
如果将遍历对`应项映射脚标`所`对应的值取反`做标记,当如果再有同样`应项映射脚标`所`对应的值`为负数时候说明已经在当前数组找过一次因此可以断定为重复值
* 前半程映射
* 后半程映射
>[danger] ##### js 解题
~~~
var findDuplicates = function (nums) {
return nums.reduce((acc, cur, index, arr) => {
// 获取下角标，因为下角标被变成负数因此需要做绝对值
const key = Math.abs(cur)
arr[key - 1] *= -1
// 判读大于等于0说明出现第二次 从负数变为整数
if (arr[key - 1] >= 0) {
acc.push(key)
}
return acc
}, [])
}
~~~
>[danger] ##### java
~~~ java
import java.util.List;
import java.util.ArrayList;
public class Solution {
public List<Integer> findDuplicates(int[] nums){
List<Integer> res = new ArrayList<>();
for(int i=0;i< nums.length;i++){
// 下角标key
int key = Math.abs(nums[i]);
// 对应值映射的下角标存储的值变为负数
nums[key-1]*=-1;
if(nums[key-1]>=0){
res.add(key);
}
}
return res;
}
}
~~~
>[info] ## 题解二
整体思路和`题解一思想是一样`的只要`通过某种形式将反复出现值进行操作`，和`单次操作`的值进行`对比`取出`双次操作`的值即可
将`对应值`所映射的`脚标值`这次从取反变成`加当前数组长度`,如果出现两次那么就会`加两次当前数组长度值`，那么出现`两次值所映射对应值`一定会`大于当前长度的两倍`
剩下问题就是之前只是单纯的取反，因此获取值的时候`index`只需要获取`绝对值`即可找到对应映射值，现在思路就是需要利用`取余进行`,即**index=(当前值-1)%长度**
**注**: (值)取余(取余值) 值 < 取余值 取余结果为**值** 举个例子 **6 % 7 = 6**
>[danger] ##### js 解法
~~~
// /**
// * @param {number[]} nums
// * @return {number[]}
// */
var findDuplicates = function (nums) {
// 将映射值都进行加当前数组长度
const {length} = nums
for(let num of nums){
// 取余获取映射index
const index = (num-1) % length
nums[index] +=length
}
// 找到所有大于等于 2*length
return nums.reduce((acc,cur,index)=>{
if(cur>length*2) acc.push(index+1)
return acc
},[])
}
~~~
>[danger] ##### java
~~~
import java.util.List;
import java.util.ArrayList;
public class Solution {
public List<Integer> findDuplicates(int[] nums){
List<Integer> res = new ArrayList<>();
int len = nums.length;
// 将数组进行累加当前长度
for(int i=0;i<len;i++){
// 利用取余获取实际index
int idx = (nums[i]-1) % len;
nums[idx] +=len;
}
for(int i=0;i<len;i++){
// 出现两次会累加两次当前长度因此会大于2n
if(nums[i]>2*len) res.add(i+1);
}
return res;
}
}
~~~
>[success] # 总结
为了满足题中说的空间复杂度达到**常量**级别，因此需要以自身为容器进行，数组在使用上也是和**Map** 一样是**key value**的结构，因此其实可以将数组抽化为一个映射容器作为计算
类似其他的解题方法，像题中指定了 n 的范围 `1 <= n <= 10^5` 也可将每个数加10^5,遇到大于10^5 值在减掉和第一种思路一样只是使用了极限值
- 刷题准备
- 统计数组中元素出现次数
- Leetcode -- 442数组中重复的数据
- leetcode -- 448 找到所有数组中消失的数字
- 字符类似题
- Leetcode -- 1002 查找共用字符
- Leetcode -- 1370上升下降字符串
- 指针类题解
- Leetcode -- 283 移动零
- Leetcode -- 26. 删除有序数组中的重复项
- Leetcode -- 80. 删除有序数组中的重复项 II
- Leetcode -- 27. 移除元素
- Leetcode -- 344. 反转字符串
- Leetcode -- 125 验证回文串
- Leetcode -- 11 盛最多水的容器
- Leetcode -- 1480. 一维数组的动态和