题目难度: 简单
今天我们开始一个全新的主题, 那就是 leetcode 的剑指 offer 系列, 这个系列大部分题目的出现频率都相当高, 必刷, 必刷, 必刷 👏👏👏 (重要的事情说三遍)
若无意外, 每天晚上 6 点 45 分准时更新, 中间可能会穿插一些周赛系列 (如果我参加的了话 😂). 大家在我的公众号"每日精选算法题"中的聊天框中回复 offer 就能看到该系列当前已经更新的文章了
大家有什么想法建议和反馈的话欢迎随时交流, 包括但不限于公众号聊天框/知乎私信评论等等~
题目描述
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0 ～ n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
2 <= n <= 100000
题目样例
示例
输入
[2, 3, 1, 0, 2, 5, 3]
输出
2 或 3
题目思考
- 题目中给出了每个数的取值范围, 这对我们有什么启发?
解决方案
思路
- 分析
- 相信大家都能想到使用集合存储已有数字的办法, 就是遍历的过程中如果发现数字已在集合就说明该数字重复, 否则就将数字加入集合.
- 但这样一是需要 O(N)空间, 二是完全利用不到每个数的取值范围为
0~n-1这一条件, 肯定不是面试官心里的最优答案 - 时间复杂度 O(N)应该是没法降低了, 因为最差情况就是最后两个数字是重复的, 我们至少需要扫描整个数组一遍
- 所以我们只能在空间复杂度上做文章, 看能否降低到 O(1) 空间
- 实现
- 注意数字范围在
0~n-1之间, 这说明每个数都可以放到等同于其自身值的下标中 - 所以做法很简单, 我们遇到一个值
nums[i]不等于自身下标i的数时, 我们就将nums[i]作为下标的值(也即nums[nums[i]])与当前值进行交换, 这样就保证nums[i] = nums[nums[i]]; 然后对于新的nums[i], 我们继续这一过程, 直到nums[i]也等于i为止, 这样就保证了下标和值相等. 继续往下遍历i, 重复这一过程直到发现重复数字为止 - 至于如何发现重复也很简单, 如果本身就有
nums[i] == nums[nums[i]]的话, 自然说明nums[i]就是重复项 (因为i!=nums[i]是前提条件), 直接返回nums[i]即可 - 注意题目保证了一定有重复, 所以最后外层循环之外一定不可达 (否则就没重复了), 不需要 return; 如果题目改成不存在重复就返回-1, 那直接在外层循环结束后加上
return -1即可 - 下面代码中对每一步都有详细注释, 方便大家理解
- 注意数字范围在
复杂度
- 时间复杂度
O(N)- 每个数字最多被访问两次(判断值和下标是否相等, 以及交换使得值和下标相等), 所以这里虽然看上去有两重循环(外层 for, 内层 while), 时间复杂度却为 O(N)
- 空间复杂度
O(1)- 原地更改数组, 只使用了几个变量
代码
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
for i in range(len(nums)):
# 从头开始遍历数组
while i != nums[i]:
# 当前下标i和值nums[i]不相等, 进入/继续内层循环
j = nums[i]
if nums[i] == nums[j]:
# 前提条件: i!=j, 所以nums[i]和nums[j]是数组的两个数字, 它们值相等, 即为重复数字
return nums[i]
# 交换两个值, 使得nums[j] == j, 这样可以继续循环判断i和新的nums[i]
nums[i], nums[j] = nums[j], nums[i] 大家可以在下面这些地方找到我~😊
我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊
京公网安备 11010502036488号