sourcecode

알고리즘: 어레이에서 중복 정수를 효율적으로 삭제하는 방법

copyscript 2022. 8. 30. 22:25
반응형

알고리즘: 어레이에서 중복 정수를 효율적으로 삭제하는 방법

나는 마이크로소프트와의 인터뷰에서 이 문제를 얻었다.

임의의 정수 배열을 지정하면 중복된 번호를 삭제하고 원래 배열의 고유 번호를 반환하는 알고리즘을 C에 작성합니다.

입력: :: 력:{4, 8, 4, 1, 1, 2, 9} ★★★★★{4, 8, 1, 2, 9, ?, ?}

한 가지 주의할 점은 예상되는 알고리즘에서 어레이를 먼저 정렬할 필요가 없다는 것입니다.그리고 요소가 제거되면 다음 요소도 앞으로 이동해야 합니다.어쨌든 요소가 앞으로 이동된 배열의 끝부분에 있는 요소의 값은 무시할 수 있습니다.

업데이트: 결과는 원래 배열로 반환되어야 하며 도우미 데이터 구조(해시 테이블 등)는 사용하지 않아야 합니다.하지만 주문보존은 필요없다고 생각합니다.

업데이트 2:왜 이런 비실용적인 제약이 있는지 궁금하신 분들은 인터뷰 질문이었고, 어떻게 하면 다른 아이디어를 낼 수 있을지 고민하는 과정에서 이 모든 제약이 논의됩니다.

전에 SO에 올린 적이 있는데, 꽤 멋있어서 여기에 다시 올려볼게요.해시를 사용하여 해시 집합과 같은 것을 만듭니다.액와공간의 O(1)가 보증되며(재귀는 테일콜), 통상은 O(N)시간 복잡도입니다.알고리즘은 다음과 같습니다.

  1. 배열의 첫 번째 요소를 가져가라. 이것이 초병이 될 것이다.
  2. 가능한 한 배열의 나머지 부분을 정렬하여 각 요소가 해당 해시에 해당하는 위치에 오도록 합니다.이 단계가 완료되면 중복 항목이 검색됩니다.초병과 같게 해
  3. 인덱스가 해시인 모든 요소를 배열의 선두로 이동합니다.
  4. 배열의 첫 번째 요소를 제외한 감시와 동일한 모든 요소를 배열 끝으로 이동합니다.
  5. 적절한 해시 요소와 중복 요소 사이에 남아 있는 것은 충돌로 인해 해당 해시에 해당하는 인덱스에 배치되지 못한 요소입니다.반복하여 이러한 요소를 처리합니다.

해시에 병리학적 시나리오가 없다면 O(N)로 나타낼 수 있습니다.복제가 없더라도 각 재귀에서 약 2/3의 요소가 제거됩니다.각 재귀 레벨은 O(n)입니다.작은 n은 남아 있는 요소의 양입니다.유일한 문제는 중복이 적은 경우(즉, 충돌이 많은 경우) 빠른 정렬보다 속도가 느리다는 것입니다.하지만, 엄청난 양의 중복이 있을 때, 그것은 놀라울 정도로 빠릅니다.

편집: D의 현재 실장에서는 hash_t는 32비트입니다.이 알고리즘의 모든 것은 완전한 32비트 공간에서 해시 충돌이 발생할 경우 매우 적은 것으로 가정합니다.단, 모듈러스 공간에서 충돌이 자주 발생할 수 있습니다.그러나 이 가정은 모든 적절한 크기의 데이터 세트에 해당될 가능성이 높습니다.키가 32비트 이하일 경우 자체 해시일 수 있습니다.즉, 완전한 32비트 공간에서의 충돌은 불가능합니다.용량이 더 클 경우 32비트 메모리 주소 공간에 충분히 설치할 수 없기 때문에 문제가 발생합니다.d의 64비트 구현에서는 hash_t가 64비트로 증가할 것으로 예상되며, 여기서 데이터셋은 더 커질 수 있습니다.또한 이것이 문제가 될 경우 각 재귀 수준에서 해시 함수를 변경할 수 있습니다.

다음은 D 프로그래밍 언어로 구현한 것입니다.

void uniqueInPlace(T)(ref T[] dataIn) {
    uniqueInPlaceImpl(dataIn, 0);
}

void uniqueInPlaceImpl(T)(ref T[] dataIn, size_t start) {
    if(dataIn.length - start < 2)
        return;

    invariant T sentinel = dataIn[start];
    T[] data = dataIn[start + 1..$];

    static hash_t getHash(T elem) {
        static if(is(T == uint) || is(T == int)) {
            return cast(hash_t) elem;
        } else static if(__traits(compiles, elem.toHash)) {
            return elem.toHash;
        } else {
            static auto ti = typeid(typeof(elem));
            return ti.getHash(&elem);
        }
    }

    for(size_t index = 0; index < data.length;) {
        if(data[index] == sentinel) {
            index++;
            continue;
        }

        auto hash = getHash(data[index]) % data.length;
        if(index == hash) {
            index++;
            continue;
        }

        if(data[index] == data[hash]) {
            data[index] = sentinel;
            index++;
            continue;
        }

        if(data[hash] == sentinel) {
            swap(data[hash], data[index]);
            index++;
            continue;
        }

        auto hashHash = getHash(data[hash]) % data.length;
        if(hashHash != hash) {
            swap(data[index], data[hash]);
            if(hash < index)
                index++;
        } else {
            index++;
        }
    }


    size_t swapPos = 0;
    foreach(i; 0..data.length) {
        if(data[i] != sentinel && i == getHash(data[i]) % data.length) {
            swap(data[i], data[swapPos++]);
        }
    }

    size_t sentinelPos = data.length;
    for(size_t i = swapPos; i < sentinelPos;) {
        if(data[i] == sentinel) {
            swap(data[i], data[--sentinelPos]);
        } else {
            i++;
        }
    }

    dataIn = dataIn[0..sentinelPos + start + 1];
    uniqueInPlaceImpl(dataIn, start + swapPos + 1);
}

내 여자친구가 제안한 해결책은 머지 종류 변형이다.유일한 수정사항은 병합 단계 동안 중복된 값을 무시한다는 것입니다.이 솔루션도 O(n log n)가 됩니다.이 방법에서는 정렬/복제 삭제가 함께 이루어집니다.하지만 그게 무슨 차이가 있는지는 잘 모르겠어요.

제 해결책은 이렇습니다.

///// find duplicates in an array and remove them

void unique(int* input, int n)
{
     merge_sort(input, 0, n) ;

     int prev = 0  ;

     for(int i = 1 ; i < n ; i++)
     {
          if(input[i] != input[prev])
               if(prev < i-1)
                   input[prev++] = input[i] ;                         
     }
}

1. O(1) 여유 공간을 사용하여 O(n log n) 시간 내에

예를 들어 다음과 같이 할 수 있습니다.

  • 먼저 O(n log n) 정렬을 수행합니다.
  • 그런 다음 목록을 한 번 훑어보고 목록의 선두에 모든 백의 첫 번째 인스턴스를 기록합니다.

ejel의 파트너가 가장 좋은 방법은 간단한 머지 스텝에 의한 일괄 머지 정렬이며, 예를 들어 입력을 개선할 수 없는 상태에서 가능한 한 효율적으로 새로운 라이브러리 함수를 작성하는 경우 도움이 될 수 있습니다.o 입력의 종류에 따라 해시 테이블을 사용하지 않고 실행합니다.하지만 사실 확인은 안 했어요.

2. O(lots) 여백 사용 O(n)시간

  • 모든 정수를 담을 수 있을 만큼 큰 0'd 배열을 선언하다
  • 대열을 한 번 훑어보다
  • 각 정수에 대해 해당하는 배열 요소를 1로 설정합니다.
  • 이미 1인 경우 해당 정수를 건너뜁니다.

이것은, 다음의 몇개의 의심스러운 전제 조건이 성립하는 경우에만 유효합니다.

  • 값싸게 메모리를 제로화하거나 ints의 크기가 ints의 수에 비해 작을 수 있습니다.
  • 사용하시는 OS에 256^sizepof(int) 메모리를 요청하시면 됩니다.
  • 그리고 만약 그것이 거대하다면 매우 효율적으로 당신을 위해 캐슁할 것이다.

잘못된 답변이지만 입력 요소가 많지만 모두 8비트 정수(또는 16비트 정수)인 경우 최선의 방법이 될 수 있습니다.

3. O(작은)-공간, O(n)-시간

#2로 해쉬 테이블을 사용합니다.

4. 명확한 방법

요소의 수가 적은 경우, 다른 코드의 기입과 판독이 고속인 경우는, 적절한 알고리즘을 쓰는 것은 도움이 되지 않습니다.

예를 들어 각 고유 요소(즉, 첫 번째 요소, 두 번째 요소(첫 번째 요소 제거된 요소의 중복)에 대해 어레이를 살펴봅니다.O(1) 추가 공간, O(n^2) 시간.

예. 이 기능을 수행하는 라이브러리 기능을 사용합니다.효율성은 쉽게 구할 수 있는 것에 달려 있습니다.

Java 버전은 다음과 같습니다.

int[] removeDuplicate(int[] input){

        int arrayLen = input.length;
        for(int i=0;i<arrayLen;i++){
            for(int j = i+1; j< arrayLen ; j++){
                if(((input[i]^input[j]) == 0)){
                    input[j] = 0;
                }
                if((input[j]==0) && j<arrayLen-1){
                        input[j] = input[j+1];
                        input[j+1] = 0;
                    }               
            }
        }       
        return input;       
    }

이것은 O(N log N) 알고리즘으로 한 번에 실행할 수 있으며 추가 스토리지는 필요하지 않습니다.

에서 됩니다.a[1]로로 합니다.a[N]각 스테이지 ★★★★★★★★★★★★★★★★★★★★i의 모든 " " " " "a[i]a[0] through를 통해.a[j] 두 지수 편, 두 . . . . . .j(0)을)

a[i]합니다. 힙은 하고 있습니다.a[0]로로 합니다.a[j+1]때 가 있는 a[k]을 가지는 는, 「」를 .입하삽a[i]에 삽입(즉 않으면 할 수 있습니다.하여 "Heap"으로 구성됩니다. 그렇지 않으면 힙에 삽입합니다. 힙은 현재 하나의 요소로 증가하여 현재 구성되었습니다.a[0]로로 합니다.a[j+1] " j.

합니다.i까지, 하게 됩니다.a[0]로로 합니다.a[j]j는 힙의 마지막 요소의 인덱스이며 힙에는 고유한 요소 값만 포함되어 있습니다.

int algorithm(int[] a, int n)
{
    int   i, j;  

    for (j = 0, i = 1;  i < n;  i++)
    {
        // Insert a[i] into the heap a[0...j]
        if (heapInsert(a, j, a[i]))
            j++;
    }
    return j;
}  

bool heapInsert(a[], int n, int val)
{
    // Insert val into heap a[0...n]
    ...code omitted for brevity...
    if (duplicate element a[k] == val)
        return false;
    a[k] = val;
    return true;
}

예를 들어 어레이가 원래 요소의 순서를 유지하기 때문에 이것은 요구된 것과 완전히 다릅니다.그러나 이 요건이 완화되면 위의 알고리즘이 유효합니다.

를 수 있는 는, C++ 에의 .std::sort이어서 할 것을 요구하다std::unique이치노시간 복잡도는 정렬의 경우 O(N log N), 고유 트래버설의 경우 O(N)입니다.

또한 C++가 테이블에서 제외되어도 동일한 알고리즘이 C로 작성되는 것을 막을 수 있는 것은 없습니다.

함수의 반환 값은 고유한 요소의 수가 되어야 하며, 이러한 요소는 모두 배열 전면에 저장됩니다.이 추가 정보가 없으면 중복이 있었는지조차 알 수 없습니다.

외부 루프의 각 반복은 어레이의 1개의 요소를 처리합니다.중복되지 않는 경우에는 배열의 맨 앞에 남아 있고 중복된 경우에는 배열에서 마지막으로 처리되지 않은 요소에 의해 덮어씁니다.이 용액은 O(n^2)시간 내에 실행됩니다.

#include <stdio.h>
#include <stdlib.h>

size_t rmdup(int *arr, size_t len)
{
  size_t prev = 0;
  size_t curr = 1;
  size_t last = len - 1;
  while (curr <= last) {
    for (prev = 0; prev < curr && arr[curr] != arr[prev]; ++prev);
    if (prev == curr) {
      ++curr;
    } else {
      arr[curr] = arr[last];
      --last;
    }
  }
  return curr;
}

void print_array(int *arr, size_t len)
{
  printf("{");
  size_t curr = 0;
  for (curr = 0; curr < len; ++curr) {
    if (curr > 0) printf(", ");
    printf("%d", arr[curr]);
  }
  printf("}");
}

int main()
{
  int arr[] = {4, 8, 4, 1, 1, 2, 9};
  printf("Before: ");
  size_t len = sizeof (arr) / sizeof (arr[0]);
  print_array(arr, len);
  len = rmdup(arr, len);
  printf("\nAfter: ");
  print_array(arr, len);
  printf("\n");
  return 0;
}

N*(N-1)/2로 설정합니다.일정한 추가 공간을 사용하고 원래 순서를 유지합니다.은 @Byju의 @Byju는 하지 않습니다.if(){}록. .또한 요소를 자체에 복사하지 않아도 됩니다.

#include <stdio.h>
#include <stdlib.h>

int numbers[] = {4, 8, 4, 1, 1, 2, 9};
#define COUNT (sizeof numbers / sizeof numbers[0])

size_t undup_it(int array[], size_t len)
{
size_t src,dst;

  /* an array of size=1 cannot contain duplicate values */
if (len <2) return len; 
  /* an array of size>1 will cannot at least one unique value */
for (src=dst=1; src < len; src++) {
        size_t cur;
        for (cur=0; cur < dst; cur++ ) {
                if (array[cur] == array[src]) break;
                }
        if (cur != dst) continue; /* found a duplicate */

                /* array[src] must be new: add it to the list of non-duplicates */
        if (dst < src) array[dst] = array[src]; /* avoid copy-to-self */
        dst++;
        }
return dst; /* number of valid alements in new array */
}

void print_it(int array[], size_t len)
{
size_t idx;

for (idx=0; idx < len; idx++)  {
        printf("%c %d", (idx) ? ',' :'{' , array[idx] );
        }
printf("}\n" );
}

int main(void) {    
    size_t cnt = COUNT;

    printf("Before undup:" );    
    print_it(numbers, cnt);    

    cnt = undup_it(numbers,cnt);

    printf("After undup:" );    
    print_it(numbers, cnt);

    return 0;
}
Integer[] arrayInteger = {1,2,3,4,3,2,4,6,7,8,9,9,10}; 

Set set = new HashSet();
for(Integer i:arrayInteger)
set.add(i);

System.out.println(set);

그럼 어떻게 해?

void rmdup(int *array, int length)
{
    int *current , *end = array + length - 1;

    for ( current = array + 1; array < end; array++, current = array + 1 )
    {
        while ( current <= end )
        {
            if ( *current == *array )
            {
                *current = *end--;
            }
            else
            {
                current++;
            }
        }
    }
}

O(n^2) 이하여야 합니다.

.x=arr[0]그리고 나머지 요소를 통과하여 xor 연산을 수행합니다. 0으로 하다

이렇게 하면 요소가 이전에 반복되었음을 알 수 있습니다.도 그냥 돼요.o(n)원래 배열의 모든 요소를 스캔합니다.

한층 더 효율적인 도입

int i, j;

/* new length of modified array */
int NewLength = 1;

for(i=1; i< Length; i++){

   for(j=0; j< NewLength ; j++)
   {

      if(array[i] == array[j])
      break;
   }

   /* if none of the values in index[0..j] of array is not same as array[i],
      then copy the current value to corresponding new position in array */

  if (j==NewLength )
      array[NewLength++] = array[i];
}

이 실장에서는 어레이를 정렬할 필요가 없습니다.또한 중복된 요소가 발견되면 그 이후의 모든 요소를 한 위치만 이동할 필요가 없습니다.

이 코드의 출력은 NewLength 사이즈의 array[]입니다.

여기에서는 어레이의 두 번째 요소부터 시작하여 어레이 내의 모든 요소와 이 어레이까지의 요소를 비교합니다.입력 배열을 수정하기 위한 추가 인덱스 변수 'NewLength'를 보유하고 있습니다.NewLength variabel이 0으로 초기화되었습니다.

어레이 [1]의 요소는 어레이[0]와 비교됩니다.다를 경우 어레이 [NewLength]의 값이 어레이 [1]로 변경되어 NewLength가 증가합니다.동일한 경우 NewLength는 변경되지 않습니다.

어레이 [1 2 1 3 1]가 있으면

'j' 루프의 첫 번째 경로에서는 어레이[1] (2)를 array0과 비교한 다음 어레이[NewLength] = array[1]에 2가 기록되므로 어레이는 NewLength = 2가 됩니다.

'j' 루프의 두 번째 경로에서는 어레이 [2] (1)을 array0 및 array1과 비교합니다.여기서 어레이[2] (1)과 array0은 같은 루프이므로 여기서 끊어집니다. 따라서 어레이는 NewLength = 2이므로 [1 2]가 됩니다.

등등

상위 O-notation을 찾는 경우 O(n log n) 정렬을 사용하여 어레이를 정렬하고 O(n) 트래버설을 실행하는 것이 가장 좋은 경로입니다.정렬하지 않으면 O(n^2)를 보고 있습니다.

편집: 정수만 사용할 경우 기수 정렬을 수행하여 O(n)를 얻을 수도 있습니다.

기본적인 구현은 매우 간단합니다.모든 요소를 살펴보고 나머지 요소에 중복이 있는지 확인한 후 나머지 요소를 전환합니다.

매우 비효율적이며 출력이나 정렬/바이너리 트리에 대한 도우미 배열로 속도를 높일 수 있지만 이는 허용되지 않는 것 같습니다.

메모리를 희생하는 경우는, 이것을 1회의 트래버스로 실행할 수 있습니다.해시/어소시에이션 배열에서 정수가 검출되었는지 여부를 단순히 집계할 수 있습니다.번호가 이미 표시되어 있는 경우는, 그대로 삭제해 주세요.또, 원래의 어레이로 이동하지 않는 번호를 새로운 어레이로 이동하는 것이 좋습니다.

Perl의 경우:

foreach $i (@myary) {
    if(!defined $seen{$i}) {
        $seen{$i} = 1;
        push @newary, $i;
    }
}

값을 앞뒤로 불필요하게 복사하지 않으려면 어레이를 오른쪽에서 왼쪽으로 "이동"해야 합니다.

는, 「」에 비트 할 수 .sizeof(type-of-element-in-array) / 8바이트 수: 각 비트에 해당하는 값이 이미 검출되었는지 여부를 나타냅니다.

그렇지 않으면 어레이를 통과하여 각 값을 그 뒤에 오는 값과 비교한 후 중복이 발견되면 이러한 값을 모두 삭제합니다.이것은 O(n^2) 근처(또는 O(n^2-n)/2)입니다.

IBM은 다소 가까운 주제에 대한 기사를 가지고 있다.

어디 보자:

  • O(N) 패스를 통해 최소/최대 할당 찾기
  • 검출된 비트 배열
  • O(N) 패스 스왑이 중복되어 종료된다.

자바에서는 이렇게 해결합니다.이걸 C로 어떻게 쓰는지 모르겠어요.

   int length = array.length;
   for (int i = 0; i < length; i++) 
   {
      for (int j = i + 1; j < length; j++) 
      {
         if (array[i] == array[j]) 
         {
            int k, j;
            for (k = j + 1, l = j; k < length; k++, l++) 
            {
               if (array[k] != array[i]) 
               {
                  array[l] = array[k];
               }
               else
               {
                  l--;
               }
            }
            length = l;
         }
      }
   }

아래는 어떻습니까?

int* temp = malloc(sizeof(int)*len);
int count = 0;
int x =0;
int y =0;
for(x=0;x<len;x++)
{
    for(y=0;y<count;y++)
    {
        if(*(temp+y)==*(array+x))
        {
            break;
        }
    }
    if(y==count)
    {
        *(temp+count) = *(array+x);
        count++;
    }
}
memcpy(array, temp, sizeof(int)*len);

모든 것을 원래의 어레이로 복사하기 전에 temp 어레이를 선언하고 요소를 넣습니다.

문제를 검토한 후, 여기 도움이 될 수 있는 델파이 방법이 있습니다.

var
A: Array of Integer;
I,J,C,K, P: Integer;
begin
C:=10;
SetLength(A,10);
A[0]:=1; A[1]:=4; A[2]:=2; A[3]:=6; A[4]:=3; A[5]:=4;
A[6]:=3; A[7]:=4; A[8]:=2; A[9]:=5;

for I := 0 to C-1 do
begin
  for J := I+1 to C-1 do
    if A[I]=A[J] then
    begin
      for K := C-1 Downto J do
        if A[J]<>A[k] then
        begin
          P:=A[K];
          A[K]:=0;
          A[J]:=P;
          C:=K;
          break;
        end
        else
        begin
          A[K]:=0;
          C:=K;
        end;
    end;
end;

//tructate array
setlength(A,C);
end;

다음의 예에서는, 문제를 해결할 수 있습니다.

def check_dump(x):
   if not x in t:
      t.append(x)
      return True

t=[]

output = filter(check_dump, input)

print(output)
True
import java.util.ArrayList;


public class C {

    public static void main(String[] args) {

        int arr[] = {2,5,5,5,9,11,11,23,34,34,34,45,45};

        ArrayList<Integer> arr1 = new ArrayList<Integer>();

        for(int i=0;i<arr.length-1;i++){

            if(arr[i] == arr[i+1]){
                arr[i] = 99999;
            }
        }

        for(int i=0;i<arr.length;i++){
            if(arr[i] != 99999){

                arr1.add(arr[i]);
            }
        }

        System.out.println(arr1);
}
    }

이것은, 입력 리스트의 정수수의 O(N) 타임과 일의의 정수수의 O(N) 스토리지로 1 패스로 실행할 수 있습니다.

첫 번째 항목에 "dst" 및 "src" 포인터를 초기화하여 목록을 앞부터 뒤까지 살펴봅니다."integers seeen"의 빈 해시 테이블로 시작합니다.src의 정수가 해시에 없는 경우 dst의 슬롯에 쓰고 dst를 늘립니다.src의 정수를 해시에 추가한 후 src를 늘립니다.src가 입력 목록의 끝에 도달할 때까지 반복합니다.

에 모든 요소를 삽입합니다.binary tree the disregards duplicates-O(nlog(n))그런 다음 트래버설을 수행하여 어레이 내의 모든 파일을 추출합니다.O(n)주문보존은 필요없다고 생각합니다.

해싱에는 블룸 필터를 사용합니다.이것에 의해, 메모리 오버헤드가 큰폭으로 삭감됩니다.

JAVA에서는

    Integer[] arrayInteger = {1,2,3,4,3,2,4,6,7,8,9,9,10};

    String value ="";

    for(Integer i:arrayInteger)
    {
        if(!value.contains(Integer.toString(i))){
            value +=Integer.toString(i)+",";
        }

    }

    String[] arraySplitToString = value.split(",");
    Integer[] arrayIntResult = new Integer[arraySplitToString.length];
    for(int i = 0 ; i < arraySplitToString.length ; i++){
        arrayIntResult[i] = Integer.parseInt(arraySplitToString[i]);
    }

출력: { 1, 2, 3, 4, 6, 7, 8, 9, 10}

이것이 도움이 되기를 바란다

복잡도가 O(n)인를 작성합니다.

먼저 어레이를 생성해야 합니다.check[n]여기서 n은 중복되지 않도록 하는 배열의 요소 수이며 모든 요소(체크 배열)의 값을 1로 설정합니다.for loop을 사용하여 중복된 어레이를 트래버스합니다.이 이름은 다음과 같습니다.arr에는 for-loop이라고

{
    if (check[arr[i]] != 1) {
        arr[i] = 0;
    }
    else {
        check[arr[i]] = 0;
    }
}

그러면 모든 중복 항목을 0으로 설정합니다. 건 이 길을 이에요.arr0으로 하다순서는 그대로 유지되며 선형 시간(3*n)이 걸립니다.

n개의 요소의 배열을 지정하면 시간 O(nlogn) 내에 배열에서 모든 중복을 제거하는 알고리즘을 작성합니다.

Algorithm delete_duplicates (a[1....n])
//Remove duplicates from the given array 
//input parameters :a[1:n], an array of n elements.

{

temp[1:n]; //an array of n elements. 

temp[i]=a[i];for i=1 to n

 temp[i].value=a[i]

temp[i].key=i

 //based on 'value' sort the array temp.

//based on 'value' delete duplicate elements from temp.

//based on 'key' sort the array temp.//construct an array p using temp.

 p[i]=temp[i]value

  return p.

기타 요소는 '키'를 사용하여 출력 배열에 유지됩니다.키의 길이는 O(n)이고 키와 값을 정렬하는 데 걸리는 시간은 O(nlogn)라고 가정합니다.따라서 어레이에서 모든 중복을 삭제하는 데 걸리는 시간은 O(nlogn)입니다.

언급URL : https://stackoverflow.com/questions/1532819/algorithm-efficient-way-to-remove-duplicate-integers-from-an-array

반응형