Выдаліце ​​дублікаты з адсартаванага масіва


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка facebook Morgan Stanley Wipro Xome Zoho
масіў

Пастаноўка праблемы

«Выдаліць дублікаты з адсартаваныя масіў »сцвярджае, што вам дадзены адсартаваны масіў памерам N. Вам неабходна выдаліць дублікаты элементаў з масіва. Раздрукуйце масіў якія ўтрымліваюць унікальныя элементы пасля выдалення паўтаральных элементаў.

Прыклад

Выдаліце ​​дублікаты з адсартаванага масіва

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

Тлумачэнне: Паколькі ўваходны масіў утрымліваў толькі 1. Адзіным выразным элементам з'яўляецца таксама толькі 1.

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

Тлумачэнне: Паўторныя 3 і 4 былі выдалены, таму выніковы масіў мае толькі {2, 3, 4}.

Падыход

Тут мы ўзялі ўжо адсартаваны масіў у якасці ўваходных дадзеных. І зараз нам трэба выдаліць дублікаты. Калі б масіў не быў адсартаваны, у ім былі б нумары, размешчаныя ў выпадковым парадку. І тады выдаленне дублікатаў было б працаёмкай задачай. Але паколькі лічбы ўжо адсартаваны ў масіве. Такім чынам, мы ўпэўнены, што калі дублікаты існуюць у масіве, яны будуць пастаянна. Гэта значыць, мы можам выбраць нумар і яго дублікаты, і яны заўсёды будуць існаваць як сумежны падмасіў. Выкарыстоўваючы гэты факт, у нас ёсць два падыходы, першы падыход займае трохі месца, але другі падыход выкарыстоўвае пачатковы масіў для памяншэння складанасці прасторы. Такім чынам, выбар любога падыходу з двух залежыць ад задачы.

Ітэратыўны метад

Алгарытм

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
Праграма Java
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.

Код для выдалення дублікатаў з адсартаванага масіва

Праграма 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
Праграма Java
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), таму што мы выкарыстоўвалі толькі пастаянную прастору і абнавілі пачатковы масіў уводу замест стварэння новага.