Премахване на дубликати от сортиран масив


Ниво на трудност Лесно
Често задавани в Амазонка Facebook Morgan Stanley Wipro Xome Zoho
Array

Декларация за проблема

“Премахване на дубликати от сортирано масив ”заявява, че ви е даден сортиран масив с размер 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

Анализ на сложността

Сложност във времето

НА), защото веднъж сме преминали първоначалния масив.

Сложност на пространството

НА) защото в най-лошия случай, когато всички елементи са различни, ще трябва да съхраняваме 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

Анализ на сложността

Сложност във времето

НА), прекосихме масива с N елемента, като по този начин алгоритъмът има решение за линейна сложност.

Сложност на пространството

O (1), тъй като сме използвали само постоянно пространство и сме актуализирали първоначалния входен масив, вместо да създаваме нов.