剑指 Offer 03. 数组中重复的数字(简单数组)

不念不忘少年蓝@ 2022-12-24 04:58 74阅读 0赞

**目录**

题目

思路1

代码

思路2

代码

提升笔记

--------------------

# 题目 #

找出数组中重复的数字。  
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：  
\[2, 3, 1, 0, 2, 5, 3\]  
输出：2 或 3

限制：

2 <= n <= 100000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof

# 思路1 #

使用List做桶统计，类似哈希表，索引与值对应。时间复杂度，空间复杂度均为O(n)。

## 代码 ##

class Solution:
        def findRepeatNumber(self, nums: List[int]) -> int:
            n = len(nums)
            cnt = [0]*n
            for num in nums:
                if cnt[num] == 1:
                    return num
                else:
                    cnt[num] = 1

# 思路2 #

由思路1可知，如果没有重复的，那么应该**索引与值一致**。我们遍历数组，如果**索引与值不一致**，那么就把**当前的值**放到应该在的**索引位置**，直到当前值与索引一致。

如果交换过程中发现**待交换位置已经放好了对应的值**，则说明重复。

示例的过程如下：

[2, 3, 1, 0, 2, 5, 3]

[1, 3, 2, 0, 2, 5, 3]

[3, 1, 2, 0, 2, 5, 3]

[0, 1, 2, 3, 2, 5, 3]

待交换位置已经放好了2，说明2重复，停止。

## 代码 ##

class Solution:
        def findRepeatNumber(self, nums: List[int]) -> int:
            n = len(nums)
            for i in range(n):
                while nums[i]!=i:
                    if nums[i] == nums[nums[i]]:
                        return nums[i]
                    nums[i] += nums[nums[i]]
                    nums[nums[i]] = nums[i] - nums[nums[i]]
                    nums[i] -= nums[nums[i]]

# 提升笔记 #

列表进行交换时，不能使用python特有的交换方式，因为Python是传址的方式，temp只是nums\[i\]的别名，地址一样。。

> >>> nums = \[2,3,1,0,2,5,3\]  
> >>> nums\[0\],nums\[nums\[0\]\] = nums\[nums\[0\]\],nums\[0\]  
> >>> nums  
> \[1, 2, 1, 0, 2, 5, 3\]

如果不明白，可以看这个，和上面的是一样的。

> >>> nums = \[2,3,1,0,2,5,3\]  
> >>> temp = nums\[0\]  
> >>> nums\[0\] = nums\[nums\[0\]\]  
> >>> nums\[nums\[0\]\] = temp  
> >>> nums  
> \[1, 2, 1, 0, 2, 5, 3\]

对于数值是可以的：

> >>> a = 2  
> >>> b = 3  
> >>> a,b = b,a  
> >>> a  
> 3  
> >>> b  
> 2

更多oj内容：[OJ网站题目分类，分难度整理笔记（leetcode、牛客网）][OJ_leetcode]

更多python相关内容：[【python总结】python学习框架梳理][python_python]

本人b站账号:[lady\_killer9][lady_killer9]

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[OJ_leetcode]: https://blog.csdn.net/lady_killer9/article/details/108273799
[python_python]: https://blog.csdn.net/lady_killer9/article/details/108763489
[lady_killer9]: https://space.bilibili.com/374432302