हटाए गए सरणी से डुप्लिकेट निकालें


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

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

“डुप्लिकेट निकालें छाँटे गए सरणी ”में कहा गया है कि आपको आकार एन का एक क्रमबद्ध सरणी दिया जाता है। आपको सरणी से डुप्लिकेट तत्वों को निकालने की आवश्यकता है। प्रिंट करें सरणी डुप्लिकेट तत्वों को हटाने के बाद अद्वितीय तत्व युक्त।

उदाहरण

हटाए गए सरणी से डुप्लिकेट निकालें

a [] = {1, 1, 1, 1}
{1}

स्पष्टीकरण: चूंकि इनपुट सरणी में केवल 1 समाहित है। एकमात्र अलग तत्व भी केवल 1 है।

a [] = {1, 3, 3, 3, 4}
{1, 3, 4}

स्पष्टीकरण: दोहराए गए 3 और 4 को हटा दिया गया, इस प्रकार परिणामी सरणी में केवल {2, 3, 4} है।

दृष्टिकोण

यहां, हमने इनपुट के रूप में पहले से ही सॉर्ट किए गए ऐरे को लिया है। और अब हमें डुप्लिकेट को हटाने की आवश्यकता है। यदि सरणी को क्रमबद्ध नहीं किया गया था, तो इसमें यादृच्छिक शैली में व्यवस्थित संख्याएँ होती। और फिर डुप्लिकेट को हटाना एक समय लेने वाला कार्य होता। लेकिन चूंकि संख्या पहले से ही सरणी में क्रमबद्ध हैं। इसलिए, हमें यकीन है कि यदि डुप्लिकेट सरणी में मौजूद हैं, तो वे एक निरंतर फैशन में होंगे। यही कारण है कि हम एक संख्या और इसके डुप्लिकेट चुन सकते हैं और वे हमेशा सन्निहित उपश्रेणी के रूप में मौजूद रहेंगे। इस तथ्य का उपयोग करते हुए हमारे पास दो दृष्टिकोण हैं, पहला दृष्टिकोण थोड़ी सी जगह लेने वाला है लेकिन दूसरा दृष्टिकोण अंतरिक्ष की जटिलता को कम करने के लिए प्रारंभिक सरणी का उपयोग करता है। इसलिए, दोनों में से किसी भी दृष्टिकोण को चुनना कार्य पर निर्भर करता है।

Iterative विधि

कलन विधि

1. Initialize an array of integer type of size n.
2. Check if n is equal to 0 or 1, return n.
3. Create another array of integer type of size n and an integer variable j as 0.
4. Traverse all the values of the original array one by one except the last element. If the value of the element at current index in array a[ ] is not equal to the value of the element at current index + 1 in array a[ ], store the element at current index in array a[ ] in new array at index j+1. 
5. Store the last element of the original array in the new array if it's unique.
6. Modify the original array by replacing its elements with the elements of new array.
7. Return the size of the new array.

एक क्रमबद्ध सरणी से डुप्लिकेट को निकालने के लिए कोड

C ++ प्रोग्राम
#include<iostream> 
using namespace std; 
  
int deleteDuplicates(int a[], int n){ 
    if(n==0 || n==1) 
        return n; 
  
    int b[n], j = 0; 
    for (int i=0; i<n-1; i++) 
        // If current element is not equal 
        // to next element then store that 
        // in new array b[]
        if (a[i] != a[i+1]) 
            b[j++] = a[i]; 
  
    // Store the last element 
    b[j++] = a[n-1]; 
  
    // copy new array in original array 
    for (int i=0; i<j; i++) 
        a[i] = b[i]; 
  
    return j; 
} 
int main(){ 
    int a[] = {1, 2, 2, 3, 4, 4, 9}; 
    int n = sizeof(a) / sizeof(a[0]); 
    n = deleteDuplicates(a, n); 
    for (int i=0; i<n; i++) 
       cout<<a[i]<<" "; 
    return 0; 
}
1 2 3 4 9
जावा प्रोग्राम
class delete{ 
    
    static int deleteDuplicates(int a[], int n){ 
        if(n==0 || n==1) 
            return n; 
       
        int[] b = new int[n]; 
          
        // Start traversing elements 
        int j = 0; 
        for (int i=0; i<n-1; i++) 
            // If current element is not equal 
            // to next element then store it 
            // in new array b[]
            if (a[i] != a[i+1]) 
                b[j++] = a[i]; 
          
        // Store the last element 
        b[j++] = a[n-1];    
          
        // copy new array in original array 
        for (int i=0; i<j; i++) 
            a[i] = b[i]; 
       
        return j; 
    } 
      
    public static void main (String[] args)  
    { 
        int a[]={1, 2, 2, 3, 4, 4, 9}; 
        int n = a.length; 
        n = deleteDuplicates(a, n); 
        for (int i=0; i<n; i++) 
           System.out.print(a[i]+" "); 
    } 
}
1 2 3 4 9

जटिलता विश्लेषण

समय जटिलता

पर), क्योंकि हमने एक बार प्रारंभिक सरणी का पता लगा लिया है।

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

पर) क्योंकि सबसे खराब स्थिति में जब सभी तत्व अलग-अलग होते हैं, तो हमें एन तत्वों को संग्रहीत करना होगा।

अंतरिक्ष कुशल विधि

कलन विधि

1. Initialize an array of integer type of size n.
2. If n is equal to 0 or 1 return n.
3. Initialize another variable temp to store the index of the next unique element.
4. Traverse all the values of the original array one by one except the last element. If the value of the current element is not equal to the next element, store the current element at index temp in the array. 
5. Store the last element at index temp in the array if it's unique.
6. Return the new array.

एक क्रमबद्ध सरणी से डुप्लिकेट को निकालने के लिए कोड

C ++ प्रोग्राम
#include<iostream> 
using namespace std; 
  
int deleteDuplicates(int a[], int n){ 
    if(n==0 || n==1) 
            return n; 
       
    int temp = 0; 
      
    for (int i=0; i<n-1; i++) 
        // If current element is not equal 
        // to next element then store it 
        // at index temp in array
        if (a[i] != a[i+1]) 
            a[temp++] = a[i]; 
      
    // Store the last element 
    a[temp++] = a[n-1];    
    return temp;  
} 
int main(){ 
    int a[] = {1, 2, 2, 3, 4, 4, 9}; 
    int n = sizeof(a) / sizeof(a[0]); 
    n = deleteDuplicates(a, n); 
    for (int i=0; i<n; i++) 
       cout<<a[i]<<" "; 
    return 0; 
}
1 2 3 4 9
जावा प्रोग्राम
class delete{ 
    
    static int deleteDuplicates(int a[], int n){ 
        if(n==0 || n==1) 
            return n; 
       
        int temp = 0; 
          
        // Start traversing elements 
        for (int i=0; i<n-1; i++) 
            // If current element is not equal 
            // to next element then store it 
            // at index temp in array
            if (a[i] != a[i+1]) 
                a[temp++] = a[i]; 
          
        // Store the last element 
        a[temp++] = a[n-1];    
        return temp; 
    } 
      
    public static void main (String[] args)  
    { 
        int a[]={1, 2, 2, 3, 4, 4, 9}; 
        int n = a.length; 
        n = deleteDuplicates(a, n); 
        for (int i=0; i<n; i++) 
           System.out.print(a[i]+" "); 
    } 
}
1 2 3 4 9

जटिलता विश्लेषण

समय जटिलता

पर), हमने एन तत्वों वाले सरणी को ट्रेस किया है इस प्रकार एल्गोरिथ्म में रैखिक जटिलता समाधान है।

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

ओ (1), क्योंकि हमने केवल निरंतर स्थान का उपयोग किया है और हमने एक नया बनाने के बजाय प्रारंभिक इनपुट सरणी को अपडेट किया है।