Tìm phần tử thiếu trong mảng đã sắp xếp các số liên tiếp trong C++

Khái niệm

Cho mảng array[] n số nguyên phân biệt, đặt theo thứ tự tăng dần liên tiếp nhưng thiếu một phần tử. Tìm phần tử thiếu.

Ví dụ 1

Đầu vào: array[] = {1, 2, 3, 4, 5, 6, 7, 9}

Đầu ra: 8

Ví dụ 2

Đầu vào: array[] = {-4, -2, -1, 0, 1, 2}

Đầu ra: -3

Ví dụ 3

Đầu vào: array[] = {1, 2, 3, 4}

Đầu ra: -1 (không thiếu)

Phương pháp

Nguyên lý

• Tìm sự không nhất quán: Hiệu giữa phần tử và chỉ số của nó phải bằng array[0] với mọi phần tử.

Ví dụ: A[] = {1,2,3,4,5} → nhất quán. B[] = {201,202,203,204} → nhất quán. C[] = {1,2,3,5,6} → không nhất quán tại C[3] vì 5-3 ≠ 1.

• Phát hiện không nhất quán giúp quét chỉ nửa mảng mỗi lần → O(log N).

Thuật toán

1. Tìm phần tử giữa, kiểm tra nhất quán.
2. Nếu giữa nhất quán: kiểm tra array[mid+1] - array[mid] > 1? Nếu có → array[mid]+1 là phần tử thiếu. Ngược lại → quét nửa phải.
3. Nếu giữa không nhất quán: kiểm tra array[mid] - array[mid-1] > 1? Nếu có → array[mid]-1 là phần tử thiếu. Ngược lại → quét nửa trái.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int findMissing(int array[], int n1) {
    int low = 0, high = n1 - 1, mid1;
    while (high > low) {
        mid1 = low + (high - low) / 2;
        if (array[mid1] - mid1 == array[0]) {
            if (array[mid1 + 1] - array[mid1] > 1)
                return array[mid1] + 1;
            else
                low = mid1 + 1;
        } else {
            if (array[mid1] - array[mid1 - 1] > 1)
                return array[mid1] - 1;
            else
                high = mid1 - 1;
        }
    }
    return -1;
}

int main() {
    int array[] = {-9, -8, -6, -5, -4, -3, -2, -1, 0};
    int n1 = sizeof(array) / sizeof(array[0]);
    cout << "Phần tử thiếu: " << findMissing(array, n1);
}

Đầu ra

Phần tử thiếu: -7