查找被移除的元素

经典算法

查找被移除的元素

阅读量: 89 编辑

公差为 1 的等差升序数列，将数列输入到程序的数组时移除了⼀个元素，导致长度为n的升序数组可能不再连续，除非被移除的是第一个或最后一个元素。需要在数组不连续时，找出被移除的元素。

【输入描述】

输入两行。第一行是数组大小 n ，第二是数组元素，用空格分开。

【输出描述】

输出若一行，输出被删除的元素。

【输入样例】

8
1 2 4 5 6 7 8 9

【输出样例】

缺失的数字是 3

【参考程序】

// 爱码岛编程
#include <iostream>
using namespace std;

const int MAXN = 10001;
int arr[MAXN];

// 找丢失的元素的值
int binarySearchMissing(int arr[], int n) {
    int left = 0;
    int right = n - 1;
    int start = arr[0];

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == start + mid) { //相等判断
            // 缺失元素在右半部分，更新左边界
            left = mid + 1;
        } else {
            // 缺失元素在左半部分，更新右边界
            right = mid;
        }
    }

    // left 和 right 都指向某个元素
    return start + left;
}


int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int missNum = binarySearchMissing(arr, n);

    if (missNum == arr[n - 1]) {
        cout << "序列是连续的" << endl;
    } else {
        cout << "缺失的数字是 " << missNum << endl;
    }

    return 0;
}