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

题目描述

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
找出数组中重复的数字。

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

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

限制：
2 <= n <= 100000

解题思路

方法1：原地置换
1、题目明确说明了数组长度为n，范围为 n-1，也就是若无重复元素排序后下标0123对应的数字就应该是0123；

2、对数组排序，其实也就是让萝卜归位，1号坑要放1号萝卜，2号坑要放2号萝卜......排序过程中查找有无重复元素。先考虑没有重复元素的情况：

 nums[i]     3  1  0  2   萝卜   
     i       0  1  2  3   坑  

0号坑说我要的是0号萝卜，不要3号萝卜，所以会去和3号坑的萝卜交换，因为如果0号坑拿了3号坑的3号萝卜，那说明3号坑装的也肯定是别人家的萝卜，所以要跟3号坑换，换完是这样的：

 nums[i]     2  1  0  3   萝卜  
     i       0  1  2  3   坑 

然而0号坑还没找到自己的萝卜，它不要2号萝卜，又去和2号坑的萝卜交换，换完是这样的：

 nums[i]     0  1  2  3   萝卜 
     i       0  1  2  3   坑  

这时候刚好就是一一对应的，交换过程也不会出现不同坑有相同编号的萝卜。要注意交换用的是while，也就是0号坑只有拿到0号萝卜，1号坑才能开始找自己的萝卜。

3、如果有重复元素，例如：

 nums[i]     1  2  3  2    萝卜
     i       0  1  2  3    坑

同样的，0号坑不要1号，先和1号坑交换，交换完这样的：

 nums[i]     2  1  3  2    萝卜
     i       0  1  2  3    坑

0号坑不要2号萝卜，去和2号坑交换，交换完这样的：

 nums[i]     3  1  2  2    萝卜
     i       0  1  2  3    坑

0号坑不要3号萝卜，去和3号坑交换，交换完这样的：

 nums[i]     2  1  2  3    萝卜
     i       0  1  2  3    坑

0号坑不要2号萝卜，去和2号坑交换，结果发现你2号坑也是2号萝卜，那我还换个锤子，同时也说明有重复元素出现。
也就是说，如果萝卜的坑被占，就是重复了，返回就好了
方法2：暴力解法，先排序，再看看有没有重复
如果排序后两个连续的数相等，就找到重复数字了。
方法3：哈希表
set里面不能存重复元素
如果添加到set的时候，发现set的长度不变，就是重复元素。

解题代码

方法1：
python

class Solution:
    def findRepeatNumber(self, nums: list[int]) -> int:
        for i in range(0, len(nums)):
            while i != nums[i]:
                if nums[i] != nums[nums[i]]:
                    change_pos = nums[i]
                    nums[i], nums[change_pos] = nums[change_pos], nums[i]
                else:
                    return nums[i]
        return 0

go

func findRepeatNumber(nums []int) int {
    for i := 0; i < len(nums); i++ {
        for i != nums[i] {
            if nums[i] != nums[nums[i]] {
                nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
            } else {
                return nums[i]
            }
        }
    }
    return 0
}

方法2：
python

class Solution:
    def findRepeatNumber(self, nums: list[int]) -> int:
        nums.sort()
        for i in range(len(nums)-1):
            if nums[i] == nums[i+1]:
                return nums[i]

go

func findRepeatNumber(nums []int) int {
    sort.Ints(nums)
    for i := 0; i < len(nums)-1; i++ {
        if nums[i] == nums[i+1] {
            return nums[i]
        }
    }
    return 0
}

方法3：
python

class Solution:
    def findRepeatNumber(self, nums: list[int]) -> int:
        nums_set = set()
        for i in range(0, len(nums)):
            nums_set.add(nums[i])
            if len(nums_set) < i + 1:
                return nums[i]

go

func findRepeatNumber(nums []int) int {
    // 创建set的方式
    type void struct{}
    var member void
    nums_set := make(map[int]void)
    for i := 0; i < len(nums); i++ {
        nums_set[nums[i]] = member
        if len(nums_set) < i+1 {
            return nums[i]
        }
    }
    return 0
}

执行结果

60ms 23.4MB
48ms 23.4MB
48ms 23.3MB

注意点

• 由于方法1中的“nums[i], nums[change_pos] = nums[change_pos], nums[i]”并不一定一次性让nums[i] = i，因此需要用一个while循环，循环到 i != nums[i]
• 问：如果数组里面压根没有0，那么怎么跳出while i != nums[i]？答：别担心，会有nums[i]等于nums[nums[i]]使得程序return nums[i]的