Created time
May 9, 2022 04:12 AM
date
status
category
Origin
summary
tags
type
URL
icon
password
slug
数组中重复的数据
给你一个长度为
n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。Find All Duplicates in an Array
Given an integer array
nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice. You must write an algorithm that runs in O(n)time and uses only constant extra space.n == nums.length
1 <= n <= 10^5
1 <= nums[i] <= n
- 「
nums中的每个元素出现 一次 或 两次」/「Each element innumsappears once or twice.」
这个题目就比较有意思，它是给我们一个整数数组，这个整数数组里面所有的数是有范围的，是1到n里面的整数，n是数组长度。这个限制是一个很强的限制，然后里面有些元素出现两次，有些元素出现一次，然后让我们找出所有出现两次的元素。要求是不能使用额外空间并且要用线性的时间复杂度解决这个问题。这个题里面就是给我们一个数组，然后数组长度是n，数组里面所有数的范围就是在1到n之间，所有数的范围都是在1到n之间，然后里面有些数出现两次，有些数出现一次，让我们找出来所有出现了两次的数。要求比较强，要求不能使用额外空间并且要要求时间复杂度是线性的。
那么这个题的话它其实是一些奇技淫巧。就是我们想一下如果我们可以使用额外空间的话，那解决这个问题就是易如反掌对吧，我们可以开一个长度是n的数组，你去记录一下每个数出现的次数就可以了，因为所有数的范围是1到n之间的，所以我们可以开一个下标是1到n的一个数组，然后从前往后遍历下每个数，统计下哪些数字是出现两次的就可以了。但是这个题不然我们用额外空间怎么办呢，那么我们就转而啊，这个啊你看啊，就相当于是我们如果说是有一个，有一片新的市场的话，那么我们赚钱就很容易对吧，那如果没有一片新的市场的话那怎么办呢，我们就会选择内卷对吧，我们就开始选择看一下能不能对我们的这个nums数组下手，答案是可以的。因为这里面他所有的数都是在1到n之间的，然后我们这里只需要，只会统计每个数出现的次数是1还是2对吧。只用判断这两种值对不对，所以我们怎么办呢？我们可以利用这个数组来去标记一下哪些数出现一次哪些数出现两次同时你还不能去丧失掉这个数组原来的存储的这个数的信息。那怎么办呢？ 我们就可以用这个原数和它的相反数来去表现出现的次数就可以了。
就是你看这个原数组里面这个样例
[4,3,2,7,8,2,3,1],下标分别是[1,2,3,4,5,6,7,8]。那比如说我们想去从小到大去遍历的时候我们4出现一次，那么我们就把第四个位置的数取一个相反数，对然后3出现一次，好那就把3这个位置的数取一个相反数，2出现一次好那就把2这个位置的数取一个相反数，然后7出现一次把第七个数取一个相反数，8出现一次诶把第八个数取一个相反数，然后2又出现一次好那把第二个位置的数再取一个相反数，就变成了正数是吧…当我们某个数从负数变成了正数的时候就说明这个数出现了两次对吧，那就找出来一个出现两次的数了。然后再看下一个3，那3又出现了一次是吧，那把第3 个数取个相反数，那第三个数是从负变成了正说明它出现了两次对吧，好那就又找出来一个，也出现了两次是吧，然后最后把第1个数取个相反数。然后我们就把所有出现两次的数都找出了一个是2一个是3对吧，所以这个题就是一个内卷化的一个经典应用，这样做的话我们没有用额外空间而且也是线性的。