CSES题集「缺失的数字」Python运行时索引越界报错修复
报错根因
IndexError: list index out of range是两个逻辑漏洞叠加导致的:
- 循环范围设置错误:你的循环定义为
range(n-1),对应arr的长度恰好是n-1,列表合法索引范围是0 ~ n-2。当循环走到最后一个迭代位(i = n-2)时,代码执行arr[i+1]会取到索引n-1,该位置超出列表的最大合法索引,直接触发越界。 - 无效的边界判断:第二版代码里写的
elif i==n-1分支永远不会被触发,因为range(n-1)生成的迭代值最大为n-2。当缺失数字是1或者n时,所有相邻元素的差值都是1,循环不会中途break,最终会执行到越界的索引取值代码。
原有排序思路的修复方案
- 调整循环遍历范围:因为要对比相邻两个元素的差值,只需要遍历到列表倒数第二个位置即可,即使用
range(len(arr)-1),从根源上避免i+1越界。 - 覆盖两端缺失的边界场景:如果遍历完所有相邻元素的差值都为1,说明缺失的数字要么是1,要么是n,根据排序后的首元素值直接判断输出即可。
修复后的排序版参考代码:
n = int(input()) arr = list(map(int, input().strip().split()))[:n-1] arr.sort(reverse=True) for i in range(len(arr)-1): if arr[i] - arr[i+1] > 1: print(arr[i] - 1) break else: if arr[0] == n: print(1) else: print(n)
无边界问题的高效解法
基于排序的方案时间复杂度为O(nlogn),对于n最大2e5的场景虽然能通过,但无需引入排序开销。可直接通过高斯求和公式计算差值,时间复杂度为O(n),全程不涉及索引操作,从根源上杜绝越界问题:
- 1到n的连续整数总和为
n*(n+1)//2 - 用该总和减去输入列表的元素总和,得到的差值就是缺失的数字
参考代码:
n = int(input()) arr = list(map(int, input().split())) total = n * (n + 1) // 2 print(total - sum(arr))
内容的提问来源于stack exchange,提问作者Xyp9x
相关产品推荐
相关产品推荐

