หาตัวเลขที่หายไป 4 ตัวในอาร์เรย์ที่มีสมาชิก 1 ถึง N ใน C++

แนวคิด

ได้รับอาร์เรย์ของจำนวนเต็มที่ไม่ซ้ำกัน โดยแต่ละจำนวนอยู่ในช่วง [1, N] ขนาดอาร์เรย์คือ (N-4) และไม่มีสมาชิกซ้ำ ดังนั้นมีตัวเลข 4 ตัวจาก 1 ถึง N ที่หายไป ให้หาตัวเลขที่หายไป 4 ตัวนี้เรียงลำดับ

อินพุต

arr[] = {3, 6, 7, 4, 10}

เอาต์พุต

1 2 5 8 9

อินพุต

arr[] = {2, 8, 4, 13, 6, 11, 9, 5, 10}

เอาต์พุต

1 3 7 12

วิธีการ

วิธี O(N) ง่ายๆ คือใช้อาร์เรย์ช่วยขนาด N เพื่อทำเครื่องหมายสมาชิกที่เข้าชม ผ่านอาร์เรย์อินพุตและทำเครื่องหมายในอาร์เรย์ช่วย สุดท้ายพิมพ์ดัชนีทั้งหมดที่ไม่ได้ทำเครื่องหมาย

แต่โจทย์ถามว่าจะแก้ด้วยพื้นที่ช่วย O(1) ยังไง?

เริ่มต้นสร้างอาร์เรย์ชื่อ helper ความยาว 4 เพื่อชดเชยตัวเลขที่หายไป 4 ตัว และเติมด้วยศูนย์ จากนั้นวนลูปจาก i=0 ถึง i <ความยาวอาร์เรย์ของอาร์เรย์ที่กำหนด และรับค่าสัมบูรณ์ของสมาชิกที่ i แล้วเก็บในตัวแปร temp ในขณะนี้จะตรวจสอบว่า:

• หากค่าสัมบูรณ์ของสมาชิกน้อยกว่าความยาวอาร์เรย์อินพุต ให้คูณ arr[temp] ด้วย -1 (เพื่อทำเครื่องหมายว่าเข้าชมแล้ว)
• หากค่าสัมบูรณ์ของสมาชิกมากกว่าความยาวอาร์เรย์อินพุต ให้ใส่ค่า helper[temp % array.length] เป็น -1 (เพื่อทำเครื่องหมายว่าเข้าชมแล้ว)

จากนั้นวนลูปอาร์เรย์อินพุต ดัชนีที่ค่ายังมากกว่าศูนย์ แสดงว่าสมาชิกนั้นไม่ได้ถูกพบในอาร์เรย์อินพุต จึงพิมพ์ค่า (index+1) ของดัชนีนั้น

ต่อมาวนลูปอาร์เรย์ helper ดัชนีที่ค่ายังมากกว่าหรือเท่ากับศูนย์ แสดงว่าสมาชิกนั้นไม่ได้ถูกพบ จึงพิมพ์ค่า (index + array.length + 1) ของดัชนีนั้น

ตัวอย่างโค้ด C++

// โปรแกรม C++ หาตัวเลขที่หายไป 4 ตัว
// ในอาร์เรย์ขนาด N ที่สมาชิกอยู่ในช่วง 1 ถึง N+4
#include <bits/stdc++.h>
using namespace std;

// หาตัวเลขหายไป 4 ตัวในเวลา O(N) และพื้นที่ช่วย O(1)
void missing4(int arr1[], int n1) {
    // ติดตาม 4 ตัวเลขที่เป็นไปได้ซึ่งมากกว่าความยาวอาร์เรย์อินพุต
    // ใน Java helper จะถูกเริ่มต้นเป็น 0 อัตโนมัติ
    int helper[4];
    
    // เข้าชมอาร์เรย์อินพุตและทำเครื่องหมาย
    // สมาชิกที่เข้าชมแล้ว ทำให้เป็นลบใน arr[] หรือ helper[]
    for (int i = 0; i < n1; i++) {
        int temp1 = abs(arr1[i]);
        // หากสมาชิกน้อยกว่าหรือเท่ากับความยาว ทำเครื่องหมายใน arr1[]
        if (temp1 <= n1)
            arr1[temp1 - 1] *= (-1);
        // ทำเครื่องหมายใน helper[]
        else if (temp1 > n1) {
            if (temp1 % n1 != 0)
                helper[temp1 % n1 - 1] = -1;
            else
                helper[(temp1 % n1) + n1 - 1] = -1;
        }
    }
    
    // พิมพ์สมาชิกทั้งหมดที่ไม่ได้ทำเครื่องหมาย
    for (int i = 0; i < n1; i++)
        if (arr1[i] > 0)
            cout << (i + 1) << " ";
    for (int i = 0; i < 4; i++)
        if (helper[i] >= 0)
            cout << (n1 + i + 1) << " ";
    return;
}

// โค้ดหลัก
int main() {
    int arr1[] = {2, 8, 4, 13, 6, 11, 9, 5, 10};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    missing4(arr1, n1);
    return 0;
}

เอาต์พุต

1 3 7 12