[알고리즘] 배열 에서 중복 숫자 찾기 - C \ # 구현

중복 숫자 찾기
보조 배열 방식
교환 위치 방식
이분 검색 방식
 
중복 숫자 찾기
길이 가 N 인 배열 에 저장 0~N-1 간 의 숫자 중 일 부 는 중복 되 지만 어떤 숫자 가 중복 되 고 반복 되 는 지, 어떻게 중복 되 는 숫자 를 찾 을 수 있 는 지 모르겠다.
가장 간단 한 방법 은 모든 숫자 를 차례대로 옮 겨 다 니 며 뒤에 이 숫자 와 같은 숫자 가 있 는 지 확인 할 수 있다.또는 정렬 후 같은 숫자 가 있 는 지 확인 합 니 다.그러나 이런 방식 은 시간 복잡 도가 너무 높 아서 뒤에 다른 실현 방식 을 제시 하고 다음 과 같은 실현 은 경 계 를 완전히 처리 하지 않 고 주요 절차 코드 만 제시한다.찾 았 을 때 해당 하 는 숫자 를 되 돌려 줍 니 다. 그렇지 않 으 면 - 1 을 되 돌려 줍 니 다.
보조 배열 방식
보조 배열 을 통 해 배열 의 모든 요 소 를 차례대로 옮 겨 다 니 며 해당 하 는 위치 에 저장 하고 해당 하 는 위치 에 숫자 가 있 으 면 중복 되 는 숫자 를 찾 았 다 는 것 을 설명 합 니 다.이 방식 의 공간 복잡 도 O(N).

public int FindWithArray(int[] arySource_)
{
    Debug.Assert(arySource_ != null);

    int[] aryDest = new int[arySource_.Length]; // All Zero
    aryDest[0] = -1; // Ensure differ with default
    for(int i=0;i

교환 위치 방식
배열 을 재 구성 하 는 방식 으로 이 루어 진다.배열 의 모든 숫자 를 처음부터 끝까지 옮 겨 다 니 며 아래 표 시 된 i (값 을 v 로 설정) 의 값 이 i (즉 i = v) 와 같 는 지 비교 합 니 다. 같 으 면 다음 숫자 를 옮 겨 다 닙 니 다. 그렇지 않 으 면:

아래 표 시 된 v 의 값 을 보고 v 라면 찾 았 습 니 다.

그렇지 않 으 면 v 와 i 의 값 을 교환 한 다음 에 앞의 조작 을 반복 합 니 다.이 방식 은 두 가지 순환 이 있 지만 시간 복잡 도 는 O(N) (숫자 당 최대 두 번 교환 하고 자신의 위치 에 놓 았 다) 에 불과 하고 공간 복잡 도 는 O(1) 에 불과 하 다.배열 자체 가 달라 집 니 다.

void Swap(ref int nFirst_, ref int nSecond_)
{
    int nTmp = nFirst_;
    nFirst_ = nSecond_;
    nSecond_ = nTmp;
}

public int FindWithSwap(int[] arySource_)
{
    Debug.Assert(arySource_ != null);

    for(int i=0;i 

이분 검색 방식
2 분 의 검색 방식 을 빌려 숫자 수량 을 통계 한다.먼저 숫자 를 2 middle=(max-min)/2+max 로 나 누 어 [min, middle] 간 의 숫자 수량 을 통계 한다.

수량 이 middle-min+1 보다 많 으 면 중복 숫자 가 존재 합 니 다. min = max 라면 중복 숫자 를 찾 을 수 있 습 니 다.그렇지 않 으 면 [min, middle] 범위 내의 숫자 를 계속 찾 습 니 다.

그렇지 않 으 면 [middle, max] 범위 내의 숫자 를 찾 습 니 다.이 방식 의 시간 복잡 도 는 O(NlogN) (getBiCount 최대 logN 회 호출), 공간 복잡 도 O(1) 이다.

int getBiCount(int[] arySource_, int nLow_, int nHigh_)
{
    int nCount=0;
    for(int i=0; i= nLow_ && arySource_[i] <= nHigh_)
            ++nCount;
    }
    return nCount;
}

public int FindWithBiCount(int[] arySource_, int nMin, int nMax)
{
    Debug.Assert(arySource_ != null && arySource_.Length > 0);

    if (nMin > nMax)
    {
        Console.WriteLine("Min must less than Max");
        return -1;
    }
    if( nMax-nMin+1 > arySource_.Length)
    {
        Console.WriteLine("Digital interval must less than array-len");
        return -1;
    }
    while(nMin <= nMax)
    {
        int nMiddle = (nMax - nMin) / 2 + nMin;
        int nCount = getBiCount(arySource_, nMin, nMiddle);
        if(nMin == nMax)
        {
            if (nCount > 1) return nMin;
            break;
        }
        if (nCount > (nMiddle - nMin + 1))
            nMax = nMiddle;
        else
            nMin = nMiddle + 1;
    }

    return -1;
}