ลบองค์ประกอบออกจากอาร์เรย์: เปรียบเทียบ 2 รอบ (Two Traversals) และ 1 รอบ (One Traversal) ใน C++

วิธีที่ 1: Two Traversals (สองรอบ)

รอบที่ 1: ค้นหาตำแหน่งขององค์ประกอบที่ต้องการลบ
รอบที่ 2: เลื่อนองค์ประกอบทางขวามาย้ายซ้าย

#include <iostream>
using namespace std;

int main() {
    int arr[] = {11, 15, 6, 8, 9, 10};
    int length = sizeof(arr)/sizeof(arr[0]);
    int ele = 6;
    int i;
    
    // รอบที่ 1: ค้นหา
    for (i = 0; i < length; i++)
        if (arr[i] == ele) break;
    
    // รอบที่ 2: เลื่อน
    if (i < length) {
        length--;
        for (int j = i; j < length; j++)
            arr[j] = arr[j+1];
    }
    
    cout << "The array after deletion is " << endl;
    for (int i = 0; i < length; i++)
        cout << arr[i] << " ";
    return 0;
}

วิธีที่ 2: One Traversal (หนึ่งรอบ)

ใช้ตัวแปร pos 記錄ตำแหน่งที่พบ และเลื่อนองค์ประกอบพร้อมกันขณะค้นหา

#include <iostream>
using namespace std;

int main() {
    int arr[] = {11, 15, 6, 8, 9, 10};
    int length = sizeof(arr)/sizeof(arr[0]);
    int ele = 6;
    bool found = false;
    int pos = -1;
    
    for (int i = 0; i < length; i++) {
        if (pos != -1) {
            // พบแล้ว: เลื่อนองค์ประกอบ
            arr[pos] = arr[pos+1];
            pos++;
        } else if (arr[i] == ele) {
            // พบครั้งแรก
            pos = i;
            found = true;
        }
    }
    
    if (found) length--;
    
    cout << "The array after deletion is " << endl;
    for (int i = 0; i < length; i++)
        cout << arr[i] << " ";
    return 0;
}

ผลลัพธ์ (ทั้งสองวิธี)

The array after deletion is 11 15 8 9 10

เปรียบเทียบ

ทั้งสองวิธีมี Time Complexity เท่ากันคือ O(n) แต่ One Traversal อาจเร็วขึ้นเล็กน้อยในทางปฏิบัติเพราะวนลูปเพียงครั้งเดียว