【Code】剑指offer 03数组中重复的数字

目录

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 terminal

3、参考

2022算法岗该怎么准备？ - 知乎

2023届校招算法岗知识总结 - 知乎

机器学习面试准备

GitHub - rushter/MLAlgorithms: Minimal and clean examples of machine learning algorithms implementations 【剑指offer】高频ML/DL面试题（持续更新）_山顶夕景的博客-CSDN博客[email protected]GitHub - scutan90/DeepLearning-500-questions: 深度学习500问，以问答形式对常用的概率知识、线性代数、机器学习、深度学习、计算机视觉等热点问题进行阐述，以帮助自己及有需要的读者。 全书分为18个章节，50余万字。由于水平有限，书中不妥之处恳请广大读者批评指正。 未完待续............ 如有意合作，联系[email protected] 版权所有，违权必究 Tan 2018.06GitHub - geektutu/interview-questions: 机器学习/深度学习/Python/Go语言面试题笔试题(Machine learning Deep Learning Python and Golang Interview Questions)GitHub - amusi/Deep-Learning-Interview-Book: 深度学习面试宝典（含数学、机器学习、深度学习、计算机视觉、自然语言处理和SLAM等方向）

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）