C++ में O(1) स्पेस में 0 से N-1 के तत्वों के साथ निरंतर सरणी में डुप्लिकेट खोजें

मान लीजिए हमारे पास 0 से n-1 तक की संख्याओं की एक सूची है। एक संख्या को जितनी बार संभव हो उतनी बार दोहराया जा सकता है। हमें बिना किसी अतिरिक्त स्थान के दोहराई जाने वाली संख्याएँ ज्ञात करनी हैं। यदि n =7, और सूची का मान [5, 2, 3, 5, 1, 6, 2, 3, 4, 5] जैसा है। उत्तर 5, 2, 3 होगा।

इसे हल करने के लिए, हमें इन चरणों का पालन करना होगा -

• सूची में प्रत्येक तत्व ई के लिए, निम्न चरणों का पालन करें -
  • चिह्न :=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