โปรแกรม C++ หาตัวเลขซ้ำในเวลา O(n) และพื้นที่ O(1) - ชุดที่ 1

สมมติเรามีรายการตัวเลขจาก 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