Нусхабардориро аз массиви ҷудошуда хориҷ кунед


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Facebook Morgan Stanley Wipro Xome Зохо
тартиботи ҳарбӣ

Изҳороти мушкилот

“Таҳрирҳоро аз мураттаб карда шудааст 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

Таҳлили мураккабӣ

Мураккабии вақт

O (N), мо массиви дорои N элементро тай кардем, алгоритм ҳалли мураккабии хатиро дорад.

Мураккабии фазо

О (1), зеро мо танҳо фазои доимиро истифода кардем ва ба ҷои сохтани нав массиви ибтидоии воридшударо нав кардем.