Date
Jul 24, 2023
need_review
need_review
type
剑指 Offer（第 2 版）
undo
undo
难度
简单
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
限制：
2 <= n <= 100000解法1
暴力破解, 一个个数字遍历即可
- 结果超时, 时间复杂度, 空间复杂度
解法2
增加空间复杂度, 将数字加入新列表
- 时间复杂度, 空间复杂度
算法可以通过说明, 重复的数字并不在很长的列表的最后端, 所以没有超时
解法3
先使用归并排序, 再遍历一次这样的话时间复杂度是
- 结果超时
解法4 正确解法1
和解法2类似, 但是使用哈希表, 这样的话时间复杂度减到, 空间复杂度为
解法5 正确解法2
审题很重要, 因为数字列表长度为n, 列表中的数字范围[0, n-1], 完全可以用列表index来对应.
使用原地交换的方法, 就不需要额外的空间了
算法步骤:
- 不停使用nums[nums[i]]和nums[i]交换位置, 直到nums[i]==i.
- i+1
- 如果遇到nums[nums[i]] == nums[i], 说明重复了.
设备中存有
n 个文件，文件 id 记于数组 documents。若文件 id 相同，则定义为该文件存在副本。请返回任一存在副本的文件 id。示例 1：
提示：
0 ≤ documents[i] ≤ n-1
2 <= n <= 100000