Давталтыг массиваас устгах


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Facebook-ийн Morgan Stanley Випро фирмийн 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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

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), Учир нь бид зөвхөн тогтмол орон зайг ашиглаж байсан бөгөөд шинээр үүсгэхийн оронд анхны оролтын массивыг шинэчилсэн.