50 数组中重复的数字

题目描述

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

解题思路

方法一：哈希表

核心思想：使用哈希表记录已经出现的数字。

方法二：原地交换

核心思想：利用数字范围0到n-1的特性，将每个数字放到对应的位置，如果该位置已有相同数字，则找到重复。

时间复杂度：O(n) 空间复杂度：O(n)（哈希表）或 O(1)（原地交换）

Python 实现

# 方法一：哈希表
def duplicate_hash(nums):
    """
    找出重复数字（哈希表）
    """
    if not nums:
        return -1

    seen = set()
    for num in nums:
        if num in seen:
            return num
        seen.add(num)
    return -1


# 方法二：原地交换
def duplicate(nums):
    """
    找出重复数字（原地交换）
    """
    if not nums:
        return -1

    for i in range(len(nums)):
        # 将数字放到对应的位置
        while nums[i] != i:
            # 对应位置已经有这个数字了，说明重复
            if nums[i] == nums[nums[i]]:
                return nums[i]
            # 交换
            nums[i], nums[nums[i]] = nums[nums[i]], nums[i]

    return -1


# 测试代码
if __name__ == "__main__":
    test_cases = [
        [2, 3, 1, 0, 2, 5, 3],
        [1, 2, 3, 4, 5, 6, 7],
        [1, 1, 2, 3, 4],
    ]

    for nums in test_cases:
        result = duplicate(nums[:])
        print(f"{nums} → 重复数字: {result}")

# 输出:
# [2, 3, 1, 0, 2, 5, 3] → 重复数字: 2
# [1, 2, 3, 4, 5, 6, 7] → 重复数字: -1
# [1, 1, 2, 3, 4] → 重复数字: 1

图解

原地交换示例: [2,3,1,0,2,5,3]

i=0: nums[0]=2, 交换nums[0]和nums[2]
     [1,3,2,0,2,5,3]
     nums[0]=1, 交换nums[0]和nums[1]
     [3,1,2,0,2,5,3]
     nums[0]=3, 交换nums[0]和nums[3]
     [0,1,2,3,2,5,3]
     nums[0]=0, 完成

i=1: nums[1]=1, 完成
i=2: nums[2]=2, 完成
i=3: nums[3]=3, 完成

i=4: nums[4]=2, nums[2]=2, 相等！
     返回2