หาค่าซ้ำในอาร์เรย์คงที่ที่มีองค์ประกอบ 0 ถึง N-1 ในพื้นที่ O(1) ใน C++

สมมติว่ามีรายการตัวเลขจาก 0 ถึง n-1 ตัวเลขอาจซ้ำได้หลายครั้ง เราต้องหาตัวเลขที่ซ้ำโดยไม่ใช้พื้นที่เพิ่มเติม ถ้าค่า n = 7 และรายการเป็น [5, 2, 3, 5, 1, 6, 2, 3, 4, 5] คำตอบจะเป็น 5, 2, 3

เพื่อแก้ปัญหานี้ เราต้องทำตามขั้นตอนเหล่านี้:

• สำหรับแต่ละองค์ประกอบ e ในรายการ ทำขั้นตอนต่อไปนี้
  • sign := A[ค่าสัมบูรณ์ของ e]
  • ถ้า sign เป็นบวก ให้ทำให้เป็นลบ
  • มิฉะนั้น มันคือการซ้ำ

ตัวอย่าง

#include <iostream> 
#include <cmath> 
using namespace std; 

void findDuplicates(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        if (arr[abs(arr[i])] >= 0)
            arr[abs(arr[i])] *= -1;
        else
            cout << abs(arr[i]) << " ";
    }
}

int main() {
    int arr[] = {5, 2, 3, 5, 1, 6, 2, 3, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    findDuplicates(arr, n);
}

ผลลัพธ์

5 2 3 1