إزالة التكرارات من مجموعة مرتبة


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون Facebook مورجان ستانلي ويبرو Xome زوهو
مجموعة

المشكلة بيان

"إزالة التكرارات من فرز المصفوفة "تنص على أنك حصلت على مصفوفة مرتبة بالحجم N. أنت بحاجة إلى إزالة العناصر المكررة من المصفوفة. اطبع ملف مجموعة تحتوي على عناصر فريدة بعد إزالة العناصر المكررة.

مثال

إزالة التكرارات من مجموعة مرتبة

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

Explanation: نظرًا لأن مصفوفة الإدخال تحتوي على 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
برنامج جافا
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
برنامج جافا
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 وبالتالي فإن الخوارزمية لها حل تعقيد خطي.

تعقيد الفضاء

يا (1) ، لأننا استخدمنا مساحة ثابتة فقط وقمنا بتحديث مصفوفة الإدخال الأولية بدلاً من إنشاء واحدة جديدة.