剑指Offer 03. 数组中重复的数字

leetcode python 数组哈希表简单剑指Offer

剑指Offer

发布日期: 2020-10-23

更新日期: 2020-10-25

文章字数: 635

阅读时长: 2 分

阅读次数:

一、题目

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000

二、思路

1. 原地交换

这一题充分利用题目信息：长度为n的数组nums里的所有数字都在0 ~ n-1的范围内。通过这句话，我们可以得出结论：如果数组内不存在重复数字，那么这些数字必定是从0到n-1，也就是说数字与下标（数字与下标相等）可以是一对一的。

所以按照这个思路，我们可以对nums数组中的数组进行归位操作：将数字与以该数字为下标的位置上的数字进行交换，如果这两个数字相等，说明该数字重复，将其返回即可；否则交换。

2. 哈希表

我们依然是对数组中的元素进行遍历，使用集合来保存遍历过的元素：

使用in来判断元素是否已经在集合中，
- 为True：则将改=该值返回
- 为False：将该值添加到集合

至于为什么使用集合，因为集合背后也是哈希实现的，所以查找起来更快。

三、代码

1. 原地交换

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[nums[i]], nums[i] = nums[i], nums[nums[i]]
        return -1

提示：

代码中的值交换必须注意顺序，不能写成nums[i], nums[nums[i]] = nums[nums[i]], nums[i]。因为这样写会首先改变nums[i]的值，会导致在接下来给nums[nums[i]]的赋值位置发生改变。

详细了解可以点我

2. 哈希表

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        st = set()
        n = len(nums)
        for i in range(n):
            if nums[i] in st:
                return nums[i]
            st.add(nums[i])
        return -1