정렬 된 배열에서 중복 제거

난이도 쉽게
자주 묻는 질문 아마존 Facebook 모건 스탠리 (Morgan Stanley) 위 프로 조호 (Zoho)
배열조회수 24

문제 정책

“중복 항목 제거 분류 배열”은 크기 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
자바 프로그램
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

복잡성 분석

시간 복잡성

의 위에), 우리는 N 요소를 갖는 배열을 순회했기 때문에 알고리즘은 선형 복잡도 솔루션을 갖습니다.

공간 복잡성

O (1), 상수 공간 만 사용했고 새 배열을 만드는 대신 초기 입력 배열을 업데이트했기 때문입니다.

Translate »