目录
1、题目
2、解题
3、参考
1、题目找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
2、解题该题关键在于找出【任意】一个重复数字即可
思路：哈希表 / Set（本质一维数组） 利用数据结构特点，容易想到使用哈希表（Set）记录数组的各个数字，当查找到重复数字则直接返回。
算法流程： 初始化： 新建 HashSet ，记为 dict ； 遍历数组 nums 中的每个数字 n ： 当 n 在 dict中，说明重复，直接返回 数字n ； 否则将 未出现过的数字n添加至 dict 中；
复杂度分析：
- 时间复杂度 O(N)： 遍历数组使用 O(N) ，HashSet 添加与查找元素皆为 O(1) 。
- 空间复杂度 O(N) ： HashSet 占用 O(N) 大小的额外空间（额外申请了空间）。
下面是K神详解解题思路
def findRepeatNumber(nums):
dict = set()
for n in nums:
if n in dict:
return n
else:
dict.add(n)
nums = [2, 3, 1, 0, 2, 5, 3]
result = findRepeatNumber(nums)
print(result)
arr = input("please input some numbers with blank")
nums2 = [int(n) for n in arr.split()]
result2 = findRepeatNumber(nums2)
print(result2)结果
2
please input some numbers with blank
2 3 1 0 2 5 3
2
** Process exited - Return Code: 0 **
Press Enter to exit terminal进阶版思考
上面的方法空间复杂度为O(N)，那有没有方法降低呢？
原地交换
题目说明尚未被充分使用，即 在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 。 此说明含义：数组元素的 索引 和 值 是 一对多 的关系。
因此，可遍历数组并通过交换操作，使元素的 索引 与 值 一一对应（即 nums[i]=i ）。因而，就能通过索引映射对应的值，起到与字典等价的作用。
即在原数组的基础上让索引和索引对应的值相等，就是索引是0，值就是0，索引是1，值就是1。
算法流程：(关键在于条件判断） 遍历数组 nums ，设索引初始值为 n=0 :
若 nums[n] =n ： 说明此数字已在对应索引位置，无需交换，因此跳过，继续往下遍历执行； 若 nums[nums[n]] =nums[n] ： 代表索引 nums[n]处和索引 n处的元素值都为 nums[n] ，即找到一组重复值，返回此值 nums[n] ； 否则： 交换索引为 i和 nums[n] 的元素值，将此数字交换至对应索引位置。
复杂度分析： 时间复杂度 O(N)： 遍历数组使用 O(N) ，每轮遍历的判断和交换操作使用 O(1) 。 空间复杂度 O(1) ： 使用常数复杂度的额外空间。
代码
def findRepeatNumber(nums):
n = 0
while n < len(nums):
if nums[n] == n:
n += 1
continue
if nums[nums[n]] == nums[n]:
return nums[n]
else:
nums[nums[n]], nums[n] = nums[n], nums[nums[n]]
nums = [2, 3, 1, 0, 2, 5, 3]
result = findRepeatNumber2(nums)
print(result)
arr = input("please input some numbers with blank")
nums2 = [int(n) for n in arr.split()]
result2 = findRepeatNumber(nums2)
print(result2)结果
2
please input some numbers with blank
2 3 1 0 2 5 3
2
** Process exited - Return Code: 0 **
Press Enter to exit terminal2022算法岗该怎么准备？ - 知乎
2023届校招算法岗知识总结 - 知乎
机器学习面试准备
GitHub - rushter/MLAlgorithms: Minimal and clean examples of machine learning algorithms implementations
【剑指offer】高频ML/DL面试题（持续更新）_山顶夕景的博客-CSDN博客_recall@k GitHub - scutan90/DeepLearning-500-questions: 深度学习500问，以问答形式对常用的概率知识、线性代数、机器学习、深度学习、计算机视觉等热点问题进行阐述，以帮助自己及有需要的读者。 全书分为18个章节，50余万字。由于水平有限，书中不妥之处恳请广大读者批评指正。 未完待续............ 如有意合作，联系scutjy2015@163.com 版权所有，违权必究 Tan 2018.06 GitHub - geektutu/interview-questions: 机器学习/深度学习/Python/Go语言面试题笔试题(Machine learning Deep Learning Python and Golang Interview Questions) GitHub - amusi/Deep-Learning-Interview-Book: 深度学习面试宝典（含数学、机器学习、深度学习、计算机视觉、自然语言处理和SLAM等方向）
备战秋招，leetcode每天刷多少题比较好？ - 知乎
GitHub - MisterBooo/LeetCodeAnimation: Demonstrate all the questions on LeetCode in the form of animation.（用动画的形式呈现解LeetCode题目的思路） LeetCode 高频题！_AlgoMooc算法慕课网
BAT大佬写的Leetcode刷题笔记，看完秒杀80%的算法题！
Online Python - IDE, Editor, Compiler, Interpreter
jyd - 力扣（LeetCode）
GitHub - krahets/LeetCode-Book: 《剑指 Offer》 Python, Java, C++ 解题代码，LeetBook《图解算法数据结构》配套代码仓。
GitHub - Jack-Cherish/LeetCode: LeetCode、剑指Offer刷题笔记（C/C++、Python3实现）
GitHub - greyireland/algorithm-pattern: 算法模板，最科学的刷题方式，最快速的刷题路径，你值得拥有~ GitHub - zhulintao/CodingInterviewChinese2: 《剑指Offer》第二版源代码（Clone from: https://github.com/zhedahht/CodingInterviewChinese2）
