CSP-J 2023 第一轮 第 36 题：寻找被移除的元素：④处应填

题目

1. (寻找被移除的元素)问题: 原有长度为 $n+1$ 公差为 $1$ 等差数列，将数列输到程序的数组时移除了一个元素，导致长度为 $n$ 的连续数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。试补全程序。

#include <iostream>
#include <vector>
using namespace std;
int find_missing(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right){
        int mid = left + (right - left) / 2;
        if (nums[mid] == mid + ①) {
            ②;
        } else {
            ③;
        }
    }
    return ④;
}
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    int missing_number = find_missing(nums);
    if (missing_number == ⑤) {
        cout << "Sequence is consecutive" << endl;
    }else{
        cout << "Missing number is " << missing_number << endl;
    }
    return 0;
}

④处应填（ ）

选项

• A. left+nums[0]
• B. right+nums[0]
• C. mid+nums[0]
• D. right+1

答案

A 或 B

题解

按出题意图应选 A，但这道题不够严谨：B 也正确，因为循环结束时 left == right。

假设没有缺失，下标为 i 的元素应该是：

``cpp nums[i] == nums[0] + i ``

若移除了中间某个元素，那么：

• 缺失位置之前，上式成立；
• 缺失位置及之后，实际元素比预期大 1。

因此，用二分查找找到第一个不符合上述规律的位置：

``cpp if (nums[mid] == mid + nums[0]) { left = mid + 1; // 左半部分正常，向右找 } else { right = mid; // 第一个异常位置在 mid 或其左侧 } ``

循环结束后，left 就是这个位置，缺失值应为：

``cpp return left + nums[0]; // A ``

例如 [3, 4, 6, 7]，第一个异常位置是下标 2，缺失值就是 2 + 3 = 5。

由于此时 left == right，B 的 right + nums[0] 与 A 完全等价；若要求单选，则题目存在问题。