അടുക്കിയ അറേയിൽ നിന്ന് തനിപ്പകർപ്പുകൾ നീക്കംചെയ്യുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഫേസ്ബുക്ക് മോർഗൻ സ്റ്റാൻലി വിപ്രോ സോം Zoho
അറേ

പ്രശ്നം പ്രസ്താവന

“ഇതിൽ‌ നിന്നും തനിപ്പകർ‌പ്പുകൾ‌ നീക്കംചെയ്യുക അടുക്കി അറേ ”എന്നത് നിങ്ങൾക്ക് N തരം വലുപ്പമുള്ള ഒരു ശ്രേണി നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. നിങ്ങൾ അറേയിൽ നിന്ന് തനിപ്പകർപ്പ് ഘടകങ്ങൾ നീക്കംചെയ്യേണ്ടതുണ്ട്. അച്ചടിക്കുക ശ്രേണി തനിപ്പകർ‌പ്പ് ഘടകങ്ങൾ‌ നീക്കംചെയ്‌തതിനുശേഷം അദ്വിതീയ ഘടകങ്ങൾ‌ അടങ്ങിയിരിക്കുന്നു.

ഉദാഹരണം

അടുക്കിയ അറേയിൽ നിന്ന് തനിപ്പകർപ്പുകൾ നീക്കംചെയ്യുക

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

വിശദീകരണം: ഇൻ‌പുട്ട് അറേയിൽ‌ 1 മാത്രം അടങ്ങിയിരിക്കുന്നതിനാൽ‌, വ്യത്യസ്‌തമായ ഘടകവും 1 മാത്രമാണ്.

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

വിശദീകരണം: ആവർത്തിച്ചുള്ള 3 ഉം 4 ഉം നീക്കംചെയ്തു, അതിനാൽ ഫലമായുണ്ടാകുന്ന അറേയ്ക്ക് {2, 3, 4 only മാത്രമേ ഉള്ളൂ.

സമീപനം

ഇവിടെ, ഞങ്ങൾ ഇതിനകം അടുക്കിയ അറേ ഇൻപുട്ടായി എടുത്തിട്ടുണ്ട്. ഇപ്പോൾ നമ്മൾ തനിപ്പകർപ്പുകൾ നീക്കംചെയ്യേണ്ടതുണ്ട്. അറേ അടുക്കിയിരുന്നില്ലെങ്കിൽ, അതിന് ക്രമരഹിതമായി നമ്പറുകൾ ക്രമീകരിക്കുമായിരുന്നു. തനിപ്പകർപ്പുകൾ നീക്കംചെയ്യുന്നത് സമയമെടുക്കുന്ന ജോലിയായിരുന്നു. അക്കങ്ങൾ‌ ഇതിനകം അറേയിൽ‌ അടുക്കിയിരിക്കുന്നതിനാൽ‌. അതിനാൽ, തനിപ്പകർ‌പ്പുകൾ‌ അറേയിൽ‌ ഉണ്ടെങ്കിൽ‌ അവ തുടർച്ചയായ രീതിയിലായിരിക്കുമെന്ന് ഞങ്ങൾക്ക് ഉറപ്പുണ്ട്. അതായത് നമുക്ക് ഒരു നമ്പറും അതിന്റെ തനിപ്പകർപ്പുകളും തിരഞ്ഞെടുക്കാനാകും, അവ എല്ലായ്പ്പോഴും തുടർച്ചയായ സബ്‌റേയായി നിലനിൽക്കും. ഈ വസ്തുത ഉപയോഗിച്ച് ഞങ്ങൾക്ക് രണ്ട് സമീപനങ്ങളുണ്ട്, ആദ്യ സമീപനം അല്പം സ്ഥലം ചെലവഴിക്കുന്നതാണ്, പക്ഷേ രണ്ടാമത്തെ സമീപനം സ്ഥലത്തിന്റെ സങ്കീർണ്ണത കുറയ്ക്കുന്നതിന് പ്രാരംഭ അറേ ഉപയോഗിക്കുന്നു. അതിനാൽ, രണ്ടിന്റെയും ഏതെങ്കിലും സമീപനം തിരഞ്ഞെടുക്കുന്നത് ചുമതലയെ ആശ്രയിച്ചിരിക്കുന്നു.

ആവർത്തന രീതി

അൽഗോരിതം

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.

അടുക്കിയ അറേയിൽ നിന്ന് തനിപ്പകർപ്പുകൾ നീക്കംചെയ്യാനുള്ള കോഡ്

സി ++ പ്രോഗ്രാം
#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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), കാരണം ഞങ്ങൾ ഒരിക്കൽ പ്രാരംഭ ശ്രേണിയിലൂടെ സഞ്ചരിച്ചു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N) കാരണം ഏറ്റവും മോശം അവസ്ഥയിൽ എല്ലാ ഘടകങ്ങളും വ്യത്യസ്തമാകുമ്പോൾ, നമുക്ക് N ഘടകങ്ങൾ സംഭരിക്കേണ്ടിവരും.

ബഹിരാകാശ കാര്യക്ഷമമായ രീതി

അൽഗോരിതം

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.

അടുക്കിയ അറേയിൽ നിന്ന് തനിപ്പകർപ്പുകൾ നീക്കംചെയ്യാനുള്ള കോഡ്

സി ++ പ്രോഗ്രാം
#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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), N ഘടകങ്ങളുള്ള അറേയിലൂടെ ഞങ്ങൾ സഞ്ചരിച്ചു, അതിനാൽ അൽ‌ഗോരിതം ലീനിയർ സങ്കീർണ്ണത പരിഹാരമുണ്ട്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), കാരണം ഞങ്ങൾ സ്ഥിരമായ ഇടം മാത്രമേ ഉപയോഗിച്ചിട്ടുള്ളൂ, പുതിയൊരെണ്ണം സൃഷ്ടിക്കുന്നതിനുപകരം പ്രാരംഭ ഇൻപുട്ട് അറേ ഞങ്ങൾ അപ്‌ഡേറ്റുചെയ്‌തു.