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

题目描述

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000

方法一：哈希表（set）

解题思路：利用哈希表解决，当找到重复的数字后直接返回

代码

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        dic = set()           #创建哈希表
        for num in nums:
            if num in dic:
                return num
            dic.add(num)      #向哈希表中添加数字
        return -1

结果and总结

• 运行时间：56ms      内存消耗：22.6MB

• 注意在第一次循环的时候哈希表里是没有数字的，在边构造边查找

方法二：原地交换

解题思路：

• 方法二是个奇解，只针对于这道题目，但真的很巧妙，也是参照了别人的解法，站在巨人的肩膀上。
• 如图：当一个索引对应两个值的时候，该值就重复了，把重复值输出即可。

• 首先，我们要将每个值对应该值的索引，达到如下图目的：

• 要达到该目的，我们就要把值交换位置，nums[nums[i]], nums[i] = nums[i], nums[nums[i]] 这段代码就是在做这个事。例如：记num[i] =a，num[num[i]]=num[a]=b,那么交换后，num[i]=b, num[num[i]]=num[a]=a,这时候下标 a 对应的元素也是a，达到目的；题目中的列表，只要三次交换后就可达到元素值对应下标值，找到重复的数字。

代码

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        i = 0
        while i<len(nums):
            if nums[i] == i:
                i += 1                  #在下标值对应元素值后，i下移，对应下一个下标
                continue
			#当 ==下标为i的值== 和 下标为 ==下标为i的值== 的值相等时，即找到两个重复的值，返回nums[i]（注意这里有个套娃）
            if nums[nums[i]] == nums[i]:    
                return nums[i]
            nums[nums[i]], nums[i] = nums[i], nums[nums[i]]     #见解题思路第四点讲解
        return -1

结果and总结

• 运行时间：60ms      内存消耗：22.6MB
• 这种方法对应其他问题的数组时就会报错，例如nums = [1,2,3,5,1]时，数值5要大于最大索引值4，运行时会报出如下图的错误，列表索引超出范围。

• 但这时我们就要注意审题了，长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内，所以nums = [1,2,3,5,1]这个数组其实是不符合题意的，5超出了0~4的范围，故而这个解法真的很巧妙！

小结

两者的运行时间和内存消耗其实都是差不多的，但解法二真的很巧妙，一个巧字，另一种方式看待问题，开括思维。觉得巧妙的小伙伴，请在评论区打出巧妙~

最后

以上就是忐忑飞机为你收集整理的LeetCode刷题__剑指 Offer 03. 数组中重复的数字（亲测有效）LeetCode 剑指 Offer 03. 数组中重复的数字方法二：原地交换的全部内容，希望文章能够帮你解决LeetCode刷题__剑指 Offer 03. 数组中重复的数字（亲测有效）LeetCode 剑指 Offer 03. 数组中重复的数字方法二：原地交换所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。