求助修正数组重复数字识别的求和差值算法问题

问题概述 #

• 需求：数组包含1到N（N∈{20000,40000,60000,80000,100000}）的连续数值，且存在一个重复数字，需找出该重复数。
• 已实现算法：
  • 暴力解法：两层嵌套循环比较所有元素对查找重复值；
  • 改进解法1（带排序）：先排序数组，再检查相邻元素找重复；
  • 改进解法2（无排序求和法）：利用1~N的求和特性，通过实际求和与预期求和的差值定位重复数。
• 当前问题：改进解法2的find_difference_between_sums函数无法正确识别固定测试重复数5，需修正。

原代码问题分析 #

1. 求和函数初始化错误：array_fatorial_add函数中result初始值设为1，导致实际求和结果多了1，差值计算完全错误；
2. 测试场景与需求不符：create_array_with_duplicate函数是替换数组中一个元素为5（数组长度仍为N），这属于“缺失一个数+重复一个数”的场景，而非需求描述的“包含1~N所有数+一个重复数”（数组长度应为N+1）；
3. 差值计算逻辑错误：原函数计算expected_sum - actual_sum，但在正确的重复场景下，重复数应为actual_sum - expected_sum。

修正后的代码 #

import time
import random

# 修正求和函数：初始值设为0，函数名更贴合功能
def calculate_array_sum(nums):
    result = 0
    for elemento in nums:
        result += elemento
    return result

# 修正测试数组生成函数：符合需求，生成包含1~N所有数+一个重复5的数组（长度N+1）
def create_array_with_duplicate(N):
    nums = list(range(1, N + 1))
    nums.append(5)  # 添加重复的5，确保数组包含1~N所有数且有一个重复
    random.shuffle(nums)
    return nums

def measure_time(func, nums):
    start_time = time.perf_counter()
    result = func(nums)
    end_time = time.perf_counter()
    return result, end_time - start_time

# 修正求和差值逻辑：返回实际和与预期和的差值，即重复数
def find_difference_between_sums(nums, N):
    actual_sum = calculate_array_sum(nums)
    # 预期和是1~N的和，因为数组是1~N加一个重复数
    expected_sum = (N * (N + 1)) // 2  # 用整数除法避免浮点数问题
    duplicate_num = actual_sum - expected_sum
    return duplicate_num

array_sizes = [20000, 40000, 60000, 80000, 100000]

for N in array_sizes:
    nums = create_array_with_duplicate(N)
    duplicate_num, time_taken = measure_time(lambda x: find_difference_between_sums(x, N), nums)
    print(f"改进解法2（无排序）：重复数 = {duplicate_num}, 耗时 = {time_taken:.6f} 秒")
    print()

修正说明 #

1. 求和函数修正：将result初始值改为0，确保求和结果准确；
2. 测试数组修正：改为在1_{N数组后添加一个5，生成符合需求的“包含1}N所有数+一个重复数”的数组；
3. 逻辑修正：重复数 = 实际数组和 - 1_{N的预期和，因为实际数组比1}N多了一个重复数，差值即为重复数；
4. 整数除法：用//替代/，避免浮点数精度问题（尤其当N很大时）。

如果坚持使用原测试场景（替换元素生成数组），求和法无法直接得到重复数，因为场景是“缺失一个数+重复一个数”，此时需要结合其他方法（如哈希表），但该场景不符合需求描述的“包含1到N的连续数值且存在一个重复数字”。

内容的提问来源于stack exchange，提问作者André Cunha