剑指 Offer03：数组中重复的数字

题目

题目地址：https://www.nowcoder.com/practice/623a5ac0ea5b4e5f95552655361ae0a8?tpId=13&tqId=11203&tPage=3&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

题目描述：

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为 7 的数组 {2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字 2。

相关题目：

思路

第一个想法

• 循环遍历，使用哈希表来存储结果：时间和空间复杂度都是 O(n)

好的方法

一种空间复杂度为 O(1) 的办法
用下表来进行说明：第一行（index） 是数组的索引值，由于题目说数值的范围在 0-(n-1) 区间，那么，我们使用排序这个数组，规则是这样的：

• 遍历整个数组，判读当前的索引值与在索引值位置的数是否相等
• 如原始数组是 [2, 3, 1, 0, 2, 5, 3]，index=0 的值是 2，它与索引值 index=0 不相等，所以就将 index=0 的值 2 与 index=2 的值 1 进行交换，得到第三行
• 此时 index=0 的值是 1，它与索引值 index=0 不相等，所以将 index=0 的值 1 与 index=1 的值 3 进行交换，得到第四行
• 此时 index=0 的值是 3，它与索引值 index=0 不相等，所以将 index=0 的值 3 与 index=3 的值 0 进行交换，得到第五行
• 此时 index=0 的值 是 0；index=1 的值是 1；index=2的值是 2；index=3 的值是 3；index=4 的值是 2 不符合条件，所以判读与 index=2 的值是否相等，相等的话就证明 2 就是重复的数字

代码

边界条件

• 数组为空
• 数组中数字必须在 0-(1-n) 的范围内

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        length = len(numbers)
        if length == 0 or not numbers:
            return False
        for num in numbers:
            if num > length-1 or num < 0:
                return False
        for i in range(length):
            while i != numbers[i]:
                if numbers[i] == numbers[numbers[i]]:
                    duplication[0] = numbers[i]
                    return True
                temp = numbers[i]
                numbers[i], numbers[temp] = numbers[temp], numbers[i]
        return False

OrderedDict 方法

from collections import OrderedDict
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        d = OrderedDict()
        for num in nums:
            if num not in d:
                d[num] = 1
            else:
                d[num] += 1
        for k, v in d.items():
            if v > 1:
                return k
"""
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        d = {}
        for num in nums:
            if num not in d:
                d[num] = 1
            else:
                return num
"""

Set 集合方案

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        s = set()
        for num in nums:
            if num in s:
                return num
            else:
                s.add(num)