Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ค้นหารายการที่ซ้ำกันในอาร์เรย์ใน O(n) และโดยการใช้พื้นที่พิเศษ O(1) ใน C++


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

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

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

ตัวอย่าง

#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