Xóa phần tử khỏi mảng: 2 lần duyệt vs 1 lần duyệt trong C++

Giới thiệu

So sánh 2 cách xóa phần tử khỏi mảng: dùng 2 vòng lặp (tìm kiếm + dịch chuyển) vs 1 vòng lặp (kết hợp cả hai).

Cách 1: Hai lần duyệt (Two Passes)

int deleteTwoPass(int arr[], int n, int key) {
    int pos = -1;
    
    // Pass 1: Tìm vị trí
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            pos = i;
            break;
        }
    }
    
    if (pos == -1) return n; // Không tìm thấy
    
    // Pass 2: Dịch chuyển
    for (int i = pos; i < n - 1; i++) {
        arr[i] = arr[i + 1];
    }
    
    return n - 1;
}

Cách 2: Một lần duyệt (Single Pass)

int deleteOnePass(int arr[], int n, int key) {
    bool found = false;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] == key && !found) {
            found = true;
            continue; // Bỏ qua phần tử này
        }
        if (found) {
            arr[i - 1] = arr[i]; // Dịch chuyển ngay lập tức
        }
    }
    
    return found ? n - 1 : n;
}

So sánh chi tiết

Mã nguồn hoàn chỉnh so sánh

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

int deleteTwoPass(int arr[], int n, int key) {
    int i;
    for (i = 0; i < n; i++) if (arr[i] == key) break;
    if (i == n) return n;
    for (int j = i; j < n - 1; j++) arr[j] = arr[j + 1];
    return n - 1;
}

int deleteOnePass(int arr[], int n, int key) {
    if (n == 0) return 0;
    if (arr[n-1] == key) return n - 1; // Tối ưu: key ở cuối
    
    bool found = false;
    for (int i = 0; i < n; i++) {
        if (arr[i] == key && !found) {
            found = true;
            continue;
        }
        if (found) arr[i - 1] = arr[i];
    }
    return found ? n - 1 : n;
}

void printArr(int arr[], int n) {
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr1[] = {1, 2, 3, 4, 5, 6};
    int arr2[] = {1, 2, 3, 4, 5, 6};
    int n = 6, key = 4;
    
    cout << "Goc: "; printArr(arr1, n);
    
    int n1 = deleteTwoPass(arr1, n, key);
    cout << "Two-pass: "; printArr(arr1, n1);
    
    int n2 = deleteOnePass(arr2, n, key);
    cout << "One-pass: "; printArr(arr2, n2);
    
    return 0;
}

Kết quả chạy chương trình

Goc: 1 2 3 4 5 6
Two-pass: 1 2 3 5 6
One-pass: 1 2 3 5 6

Mở rộng: Xóa TẤT CẢ phần tử = key

int deleteAllOccurrences(int arr[], int n, int key) {
    int write = 0;
    for (int read = 0; read < n; read++) {
        if (arr[read] != key) {
            arr[write++] = arr[read];
        }
    }
    return write;
}

Kết luận

One-pass tốt hơn về hiệu năng (cache locality) và mở rộng. Two-pass dễ đọc, dễ debug. Trong phỏng vấn, one-pass thể hiện tư duy tối ưu tốt hơn.