[力扣] 剑指 Offer 第四天 - 数组中重复的数字

耐心和持久胜过激烈和狂热。

题目来源

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述

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

示例

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

题目分析

根据题意，找出数组中第一个重复的数字并返回。本文使用 Go 语言去实现算法。

• 第一种方法是可以使用 map 去实现一个 set 集合，集合的特点是没有重复的元素，查找元素过程中，将每一个元素都存入 map 里，如果重复存入，说明数字重复了。
• 第二种方法是原地交换，因为数字的范围是 0 ~ n - 1，因此我们可以将数字交换到与数字对应下标的位置，例如 nums[0] = 0，将 0 交换到下标为 0 的位置，这样一来，每次交换之前先判断目标位置是否与交换值相同（特殊情况是 0 本身就在下标为 0 的位置可以略过），是则数字重复。

算法

map 实现 set 判断重复数字

• 使用 map 定义一个 set 集合。
• 遍历数组(切片)，判断元素是否存在于 set 集合里，存在则说明数字重复，循环结束，返回结果，不存在则将元素存于 set 集合里，继续遍历。
• 返回结果。

代码实现

func findRepeatNumber(nums []int) int {
    mp := make(map[int]struct{})
    res := -1
    for _, num := range nums {
        if _, ok := mp[num]; ok {
            res = num
            break
        }
        mp[num] = struct{}{}
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析

时间复杂度：O(N)，切片遍历需要 0(N) 的时间复杂度，将元素添加至 set 集合操作需要 O(1) 的时间复杂度。
空间复杂度：O(N)，使用 map 创建 set 集合需要 O(N) 的空间复杂度。

原地交换

• 初始化下标值 index。
• 循环遍历数组
  • 如果元素的位置处于对应下标值的位置(假设 nums[1] = 1)，遍历下一个元素
  • 如果待替换的元素 1 (假设 nums[4] = 1 ) 等于对应下标值的元素(假设 nums[1] = 1)，则说明数字重复了，返回结果
  • 否则交换元素，将元素交换到对应下标值的位置，再将对应下标值的位置交换过来，继续比较

代码实现

func findRepeatNumber(nums []int) int {
    index := 0
    for index < len(nums) {
        if nums[index] == index {
            index ++
            continue
        }
         if nums[nums[index]] == nums[index] {
            return nums[index]
        }
        nums[nums[index]], nums[index] = nums[index], nums[nums[index]]
    }
    return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

复杂度分析

时间复杂度：O(N)，切片遍历需要 0(N) 的时间复杂度，交换元素操作需要 O(1) 的时间复杂度。
空间复杂度：O(1)，没有使用额外的内存空间。

结尾

如果本文对你有帮助，欢迎点赞收藏加关注，如果本文有错误的地方，欢迎指出！