Python剑指Offer：不修改数组找出重复数字的两种解法

数组中重复的数字

回顾上一篇关于《剑指Offer》面试题3“数组中重复的数字”的内容，这类问题的核心在于遍历数组的同时查找满足特定条件的元素。

此外，在博客“用最复杂的方式学会数组（Python实现动态数组）”中，我们深入探讨了数组结构的本质，并手动实现了一个动态数组。

今天我们将介绍另一道来自《剑指Offer》的数组相关面试题：如何在禁止修改输入数组的前提下，找出其中重复的数字。

不修改数组找出重复的数字

题目二：不修改数组找出重复的数字

给定一个长度为 n+1 的数组，其中所有数字均位于 0 到 n 的范围内。根据鸽巢原理，数组中至少存在一个重复的数字。

任务要求是找出数组中任意一个重复的数字，但严格限制不能修改输入的原始数组。

样例：

给定长度为 8 的数组 nums = [2, 3, 5, 4, 3, 2, 6, 7]

输出结果可以是重复的数字 2 或者 3

思路

首先需要注意题目的两个关键约束：一是不能修改数组，二是只需返回任意一个重复数字。这些限制使得解题思路相比上一题有所减少：

1. 哈希表法：与上一题类似，可以创建一个哈希表。遍历原数组，若数字首次出现，则将其存入哈希表（即原数组值为 m 的数字对应哈希表下标 m）。该方法的空间复杂度为 $O(n)$。

2. 二分法：是否存在空间复杂度低于 $O(n)$ 的算法？假设没有重复数字，1 到 n 之间的每个数字应恰好出现一次。而题目保证至少有一个数字重复（出现次数大于 1）。

利用二分思想：将 1 到 n 的数字从中间值 m 分为两部分，前半部分为 1~m，后半部分为 m+1~n。统计 1~m 中的数字在数组中出现的次数，若次数大于 m，则重复数字必然在前半部分；

否则，重复数字必然在后半部分。接着对包含重复数字的区间继续二分，直到找到具体的重复数字。

思路一：哈希表

def find_duplicated_num(nums):
    """hash_map"""
    hash_map = dict()
    for i, val in enumerate(nums):
        if val in hash_map:
            return val
        hash_map[val] = i
    return False

思路二：二分法

def reduce_inter(nums2, left, right):
    """ """
    mid = (left + right) // 2
    count = 0
    length = len(nums2)
    for i in range(length):
        if (nums2[i] >= left) and (nums2[i] <= mid):
            count += 1
    if count > mid - left + 1:
        return left, mid
    else:
        return mid+1, right


def find_duplicated_num2(nums2):
    left, right = 1, len(nums2) - 1
    while left != right:
        left, right = reduce_inter(nums2, left, right)
    return left

测试

nums = [2, 3, 5, 4, 3, 2, 6, 7]
# nums_n = [5, 4, 3, 2, 6, 7]
print("思路一测试结果: ", find_duplicated_num(nums))
print("思路二测试结果: ", find_duplicated_num2(nums))

结果

思路一测试结果: 3 思路二测试结果: 3

总结

需要注意的是，这种算法不能保证找出所有重复的数字。例如对于数组 [2, 3, 5, 4, 3, 2, 6, 7]，二分法可能只返回 3 而忽略 2。

以上是不修改数组找出重复数字的 Python 实现详解，更多关于 Python 查找重复数字的资料请关注本站其他相关文章！