Уклоните дупликате из сортираног низа


Ниво тешкоће Лако
Често питани у амазонка фацебоок Морган Стенли випро Ксоме Зохо
Ред

Изјава о проблему

„Уклоните дупликате из сортирано низ “наводи да сте добили сортирани низ величине Н. Из низа морате уклонити дупликате елемената. Одштампајте поредак који садрже јединствене елементе након уклањања дуплираних елемената.

Пример

Уклоните дупликате из сортираног низа

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.

Код за уклањање дупликата из сортираног низа

Програм Ц ++
#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.

Код за уклањање дупликата из сортираног низа

Програм Ц ++
#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), јер смо користили само константан простор и ажурирали смо почетни уносни низ уместо да стварамо нови.