सबसे कुशल तरीके से एक सरणी में डुप्लिकेट का पता लगाएं


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना सेब ब्लूमबर्ग Facebook गूगल Lyft माइक्रोसॉफ्ट Paytm पॉकेट रत्न क्वालकॉम Zoho
ऐरे

समस्या का विवरण

उन सभी तत्वों को प्रदर्शित करें जो O (n) और O (1) स्पेस में सबसे कुशल तरीके से डुप्लिकेट हैं। दिया गया सरणी आकार n जिसमें 0 से n-1 तक की संख्याएँ हैं, ये संख्याएँ किसी भी समय हो सकती हैं। सबसे कुशल तरीके से एक सरणी में डुप्लिकेट का पता लगाएं। यदि यह संख्या पहले से ही सरणी में हुई है, तो संख्या डुप्लिकेट है।

उदाहरण

निवेश

23

1 5 4 2 8 4 1 0 0 2 4 9 4 2 4 6 6 7 3 1 0 0 0

उत्पादन

4 1 0 2 4 4 2 4 6 1 0 0 0

सबसे कुशल तरीके से एक सरणी में डुप्लिकेट खोजने के लिए दृष्टिकोण

अब हम समस्या को समझते हैं। तो, ज्यादा समय न लेते हुए हम सीधे समस्या के कार्यान्वयन के लिए उपयोग किए जाने वाले एल्गोरिदम की ओर बढ़ते हैं।

कलन विधि

1. शून्य की पुनरावृत्ति से निपटने के लिए एक अलग चर लें।
2. अगला, सरणी को पार करें।
3. यदि तत्व शून्य वृद्धि संख्या शून्य है। यदि गिनती 1 से अधिक है, तो इसे दोहराए गए अनुसार प्रदर्शित करें।
4. यदि यह शून्य से इतर है, तो जिस तत्व को आप खड़े कर रहे हैं, उसके निरपेक्ष मान द्वारा इंगित किए गए सरणी के इंडेक्स पर जाएं यानी अरेस्ट (एब्स (एआई [i])] और यदि यह पॉजिटिव है तो इसे नकारात्मक रूप से लागू करें वह तत्व जो सूचकांक मैं एक बार हुआ है।
5. अगर हमें कोई डुप्लिकेट मिलता है तो हम देखेंगे कि अरेस्ट (abs (एआई [i])] पहले से ही विपरीत साइन है और हम इसे प्रिंट कर सकते हैं।

कार्यान्वयन

सबसे कुशल तरीके से एक सरणी में डुप्लिकेट को खोजने के लिए C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
      cin>>arr[i];
    }
    int zero = 0; //separate case for zero
    for(int i = 0; i < N; i++)
    {
    if(arr[i] == 0)
      {
        if(zero > 0)
          cout << 0 << " ";
        
        zero++;
      }
      
    else if(arr[abs(arr[i])] >= 0)  // we take the element's value as the index and change the sign of the element at that position
    arr[abs(arr[i])] = - arr[abs(arr[i])];
    
    else    //if we have duplicates then we will encounter a location whose value is negative
     cout << abs(arr[i]) <<" ";
   }
   return 0;
}

सबसे कुशल तरीके से एक सरणी में डुप्लिकेट को खोजने के लिए जावा प्रोग्राम

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            return -1*x;
        }
        else
        {
            return x;
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int zero = 0; //separate case for zero
        for(int i = 0; i < n; i++)
        {
        if(a[i] == 0)
          {
            if(zero > 0)
              System.out.print(0+" ");
            zero++;
          }
        else if(a[abs(a[i])] >= 0)  // we take the element's value as the index and change the sign of the element at that position
        a[abs(a[i])] = - a[abs(a[i])];
        else    //if we have duplicates then we will encounter a location whose value is negative
         System.out.print(abs(a[i])+" ");
       }
    }
}
23
1 5 4 2 8 4 1 0 0 2 4 9 4 2 4 6 6 7 3 1 0 0 0
4 1 0 2 4 4 2 4 6 1 0 0 0

सबसे कुशल तरीके से एक सरणी में डुप्लिकेट का पता लगाने के लिए जटिलता विश्लेषण

समय जटिलता

पर) जहाँ N दिए गए एरे में मौजूद तत्वों की संख्या है, यहाँ हम पूरे ऐरे को पार करते हैं और अपने उत्तर की गणना करते हैं।

अंतरिक्ष जटिलता

ओ (1) क्योंकि हम परिणामों की गणना में सहायक स्थान का उपयोग नहीं करेंगे।

संदर्भ