ลบสมาชิกอาร์เรย์ด้วยสองรอบลูปและหนึ่งรอบลูปใน C++

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

รอบแรก: หาตำแหน่งของค่าที่จะลบ รอบที่สอง: เลื่อนสมาชิกหลังตำแหน่งนั้นมาหนึ่งช่อง

โค้ด

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

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

ใช้ flag บอกว่าพบค่าที่จะลบแล้วหรือยัง ถ้าพบแล้ว ให้เลื่อนสมาชิกปัจจุบันไปช่องก่อนหน้าทันที

โค้ด

int searchAndDeleteElement(int arr[], int n, int k) {
    if (arr[n-1] == k) return n - 1;
    bool isElementFound = false;
    for (int i = 0; i < n; i++) {
        if (arr[i] == k && !isElementFound) {
            isElementFound = true;
            continue;
        }
        if (isElementFound) {
            arr[i-1] = arr[i];
        }
    }
    return isElementFound ? n - 1 : n;
}

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

1 2 3 5 6

(ลบ 4 ออกจาก {1,2,3,4,5,6})

เปรียบเทียบ

สรุป

ทั้งสองวิธี O(n) แต่ One Loop มีค่าคงที่ (constant factor) น้อยกว่า เหมาะสำหรับระบบ Real-time หรือ Embedded