Tìm phần tử bị mất từ mảng trùng lặp trong C++

Khái niệm

Cho hai mảng là bản sao của nhau trừ một phần tử, nghĩa là một phần tử từ một mảng bị thiếu. Nhiệm vụ là tìm phần tử bị thiếu đó.

Đầu vào

arr1[] = {2, 5, 6, 8, 10} arr2[] = {5, 6, 8, 10}

Đầu ra

2

2 bị thiếu từ mảng thứ hai.

Đầu vào

arr1[] = {3, 4, 5, 6} arr2[] = {3, 4, 5, 6, 7}

Đầu ra

7

7 bị thiếu từ mảng đầu tiên.

Phương pháp

Giải pháp đơn giản: duyệt qua mảng và kiểm tra từng phần tử, đánh dấu phần tử thiếu khi phát hiện không khớp. Nhược điểm: cần thời gian tuyến tính theo kích thước mảng.

Giải pháp hiệu quả dựa trên tìm kiếm nhị phân:

• Bắt đầu tìm kiếm nhị phân trong mảng lớn hơn, lấy mid = (low + high) / 2
• Nếu giá trị tại mid của cả hai mảng bằng nhau, phần tử thiếu phải ở nửa phải, đặt low = mid
• Ngược lại đặt high = mid vì phần tử thiếu ở nửa trái nếu mid không bằng nhau.
• Xử lý trường hợp đặc biệt: mảng 1 phần tử hoặc 0 phần tử, chính phần tử đó là phần tử thiếu.

Nếu phần tử đầu tiên đã không bằng nhau, chính phần tử đó là phần tử thiếu.

Ví dụ

// Chương trình C++ tìm phần tử thiếu từ mảng trùng lặp (trừ 1 phần tử)
#include <bits/stdc++.h>
using namespace std;

// Hàm tìm phần tử thiếu dựa trên tìm kiếm nhị phân
// arrA[] kích thước lớn hơn, Q là kích thước của nó
// arrA[] và arrB[] giả định cùng thứ tự
int findMissingUtil(int arrA[], int arrB[], int Q){
    // Trường hợp đặc biệt: chỉ 1 phần tử thiếu trong mảng thứ hai
    if (Q == 1)
        return arrA[0];
    // Trường hợp đặc biệt: phần tử đầu tiên bị thiếu
    if (arrA[0] != arrB[0])
        return arrA[0];
    // Khởi tạo điểm mốc
    int low = 0, high = Q - 1;
    // Lặp cho đến khi low < high
    while (low < high){
        int mid = (low + high) / 2;
        // Nếu phần tử tại mid bằng nhau, đi sang mảng con bên phải
        if (arrA[mid] == arrB[mid])
            low = mid;
        else
            high = mid;
        // Nếu low, high trở thành liền kề, thoát
        if (low == high - 1)
            break;
    }
    // Phần tử thiếu sẽ ở chỉ số high của mảng lớn hơn
    return arrA[high];
}

// Hàm chính kiểm tra lỗi cơ bản và gọi findMissingUtil
void findMissing(int arrA[], int arrB[], int P, int Q){
    if (Q == P-1)
        cout << "Phần tử thiếu là " << findMissingUtil(arrA, arrB, P) << endl;
    else if (P == Q-1)
        cout << "Phần tử thiếu là " << findMissingUtil(arrB, arrA, Q) << endl;
    else
        cout << "Đầu vào không hợp lệ";
}

// Chương trình chính
int main(){
    int arrA[] = {2, 5, 6, 8, 10};
    int arrB[] = {5, 6, 8, 10};
    int P = sizeof(arrA) / sizeof(int);
    int Q = sizeof(arrB) / sizeof(int);
    findMissing(arrA, arrB, P, Q);
    return 0;
}

Đầu ra

Phần tử thiếu là 2