扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
首先想到的方法就是使用哈希表来记录每个数字出现的次数。但是这种方法需要额外空间。在访问它之前将下标为|x|-1上的数字取相反数。
十载的矿区网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。成都全网营销推广的优势是能够根据用户设备显示端的尺寸不同，自动调整矿区建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。创新互联从事“矿区网站设计”,“矿区网站推广”以来，每个客户项目都认真落实执行。
近来，我一直在刷leetcode，发现这个平台真是一个好东西。它不仅可以帮助我们提高算法水平，而且还能锻鍊我们的耐心和毅力。
今天要介绍的题目是“442. 数组中重复的数据”。这道题目给定了一个整数数组nums，其中有些元素出现两次而其他元素只出现一次。找到所有在nums中出现两次的元素。
首先想到的方法就是使用哈希表来记录每个数字出现的次数。但是这种方法需要额外空间，并且时间复杂度为O(n)。如果要达到更优秀的解决方案，则需要考虑原地修改数组。
那么如何原地修改呢？其实很简单，对于任意一个数字x，在访问它之前将下标为|x|-1上的数字取相反数。如果已经访问过该数字，则此时|x|必然小于等于n（n为数组长度），因此我们可以根据abs(nums[i])-1是否小于n来判断nums[abs(nums[i])-1]是否已经被访问过。
具体实现见代码：
```python
class Solution:def findDuplicates(self, nums: List[int]) -> List[int]:
res = []
for i in range(len(nums)):
if nums[abs(nums[i])-1]< 0:
res.append(abs(nums[i]))
else:
nums[abs(nums[i])-1] *= -1
return res
```
这里需要注意的是，我们要返回的是出现两次的元素，而不是重复元素。因此如果一个数字已经被访问过了，则它在数组中一定出现了两次。
名称栏目：每日leetcode：找出数组中的重复数据
地址分享：http://gydahua.com/article/dhpccos.html
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网