프로 그래 밍 문제 1.배열 에서 중복 되 는 숫자 찾기-O(1)공간 복잡 도 실현

제목 1:배열 에서 중복 되 는 숫자 찾기
길이 가 n 인 배열 의 모든 숫자 는 0-n-1 의 범위 내 에서 배열 의 일부 숫자 는 중복 되 지만 몇 개의 숫자 가 중복 되 었 는 지 모 르 고 모든 숫자 가 몇 번 반복 되 었 는 지 모른다.배열 에서 중복 되 는 숫자 를 찾 아 보 세 요.
자바 코드 구현:

public class ThirdQues {
     public static void main( String[] args){
         Scanner scanner = new Scanner(System.in);
         int n = scanner.nextInt();
         int a[] = new int[n] ;
         int b[] = new int[n] ;
         for( int i = 0 ; i < a.length ; i++){
             a[i] = scanner.nextInt();
         }
         for( int i = 0 ; i

이것 은 제 가 이 문 제 를 본 첫 번 째 사고 입 니 다.문제 중의 모든 숫자 는 0 에서 n-1 에 있어 서 저 에 게 큰 영감 을 주 었 습 니 다.숫자의 크기 가 이 범위 에 한정 되 어 있 기 때문에 우 리 는 이 숫자 를 새로운 배열 의 아래 표 색인 으로 할 수 있 습 니 다.새로운 배열 은 처음에 모두 0 이 었 습 니 다.색인 을 겪 은 후에 요소 의 할당 값 은 1 입 니 다.지금 여기 서 색인 을 할 수 있 습 니 다.원소 값 이 1 인 것 을 발 견 했 을 때 이 숫자 가 이미 나 타 났 다 는 것 을 설명 한다.
이 알고리즘 은 배열 을 한 번 만 옮 겨 다 니 면 됩 니 다.시간 복잡 도 는 O(n)입 니 다. ，그러나 그 는 길이 가 n 인 보조 배열 이 필요 하기 때문에 공간 복잡 도 는 O(n)이다.우 리 는 지금 더 좋 은 공간 복잡 도 알고리즘 이 있 는 지 생각 하고 있다.
마찬가지 로 0 에서 n-1 까지 저 에 게 새로운 아 이 디 어 를 주 었 습 니 다.저 는 새로운 배열 공간 을 개척 하지 않 고 원래 배열 에서 아래 표 시 된 색인 을 통 해 배열 을 다시 배열 할 수 있 습 니 다.그러면 이때 시간 복잡 도 는 여전히 O(n)이지 만 공간 복잡 도 는 O(1)가 되 었 습 니 다.

        for ( int i = 0 ; i < a.length ; i++ ){
            while( a[i] != i ){
                if( a[i] == a[ a[i]] ){
                    System.out.print(a[i]);
                    return ;
                }
                else{
                    int temp = a[i] ;
                    a[i] = a[ a[i]] ;
                    a[temp] = temp ;
                }
            }
        }

이 알고리즘 은 요소 가 있 는 위치(이 요 소 는 아래 표 색인)에 있 는 지 확인 합 니 다.없 으 면 이 요 소 를 위치 에 있 는 요소 와 비교 하고 같 으 면 이 요소 가 중복 되 고 순환 을 끝 냅 니 다.같 지 않 으 면 두 요 소 를 교환 하고 소득 요 소 를 정렬 하여 교환 합 니 다.이 알고리즘 은 두 개의 순환 을 포함 하지만 우 리 는 모든 숫자 를 최대 두 번 교환 하면 자신 만 의 위치 에 도착 할 수 있다 는 것 을 알 수 있 기 때문에 그 시간 복잡 도 는 여전히 O(n)이다.
제목 2:
n+1 길이 의 배열 에 있 는 모든 숫자 는 1~n 범위 내 에서 배열 에서 중복 되 는 숫자 를 찾 지만 입력 한 배열 을 수정 할 수 없습니다.
가장 간단 한 방법 은 당연히 보조 배열 을 만 든 다음 에 남 은 방법 은 첫 번 째 문제 의 첫 번 째 알고리즘 과 마찬가지 로 우 리 는 O(n)의 시간 에 O(n)의 보조 공간 에서 문 제 를 해결 할 수 있다.그러면 마찬가지 로 공간 소 비 를 O(1)로 낮 출 수 있 는 알고리즘 이 있 습 니까?
먼저 생각 나 는 것 은 배열 을 옮 겨 다 니 며 각 수 는 그 후의 수 와 비교 하 는 것 입 니 다.그러나 이 알고리즘 의 최 악의 경우 시간 복잡 도 는 O(n^2)입 니 다.우 리 는 더 빠 른 알고리즘 을 찾 고 싶 습 니 다.다른 길 을 찾 아야 합 니 다.
우 리 는 중복 되 는 숫자 를 찾 아야 한다.즉,이 숫자 가 두 번 이나 더 많이 나 타 났 다 는 것 을 의미한다.다시 말 하면 우 리 는 모든 숫자 가 나타 난 횟수 를 통계 할 수 있 지만 이런 시간 복잡 도 는 똑 같이 O(n^2)로 최적화 하 는 역할 을 하지 못 했다.이때 통계 횟수 를 연상 할 때 사실은 특정한 숫자 를 찾 는 것 과 같다.그러면 우 리 는 흔히 볼 수 있 는 이분 검색 법 으로 시간 복잡 도 를 O(nlogn)로 줄 일 수 있다.
다음은 자바 코드 구현:

     find(1,a.length -1  ,a );
-----------------------------------------------------------------------------------------
     
     public  static int count( int start , int end ,  int a[]){
         int count = 0 ;
         for( int i = 0 ; i=start && a[i] <= end){
                 count++ ;
             }
         }
         return count;
     }
     public static void find ( int start , int end , int a[ ]  ){
        if( start < end ){
            if( count ( start ,(start+end)/2 , a )>(start+end)/2 - start +1 ){
                find( start , (start+end)/2 ,a );
            }
            else{
                find((start+end)/2 + 1 ,end ,a);
            }
        }
        else{
            System.out.print(start);
        }

     }

우 리 는 먼저 길이 가 8 인 배열 을 두 부분 으로 나 누 었 다.즉,숫자 가 1~4 인 것 은 일부분 이 고 5~7 인 것 은 일부분 이다.그 다음 에 배열 에서 숫자 범위 가 1~4 에 속 하 는 숫자 개 수 를 조회 한 다음 에(4-1+1)보다 크 면 중복 숫자 가 나타 나 는 범 위 는 1~4 이 고 반대로 중복 숫자 가 나타 나 는 범 위 는(4+1)~7 인 것 을 설명 한 다음 에 재 귀적 으로 호출 하여 start 와 end 가 같 을 때 까지이때 start 의 값 은 중 복 된 숫자 입 니 다.이 알고리즘 은 범위 내 숫자 를 계산 할 때마다 배열 을 한 번 옮 겨 다 니 며 O(n)를 소모 합 니 다.이분법 이기 때문에 모두 nlog(n)회 를 찾 기 때문에 시간 복잡 도 는 O(nlog(n)입 니 다.이 알고리즘 은 이전 알고리즘 에 비해 시간 을 가지 고 공간 을 바 꾸 는 방법 이 고 이 알고리즘 은 모든 중복 되 는 숫자 를 찾 을 수 없습니다.예 를 들 어 배열{2,2,2,4,5,6,6}에 대해 이 알고리즘 을 실행 할 때 1~4 에 모두 4 개의 2 가 있 기 때문에 판단 조건 을 만족 시 키 기 때문에 중복 되 는 2 라 는 숫자 를 구 할 수 없습니다.
이 문 제 는 사실 아직도 많은 세부 적 인 부분 이 있다.나 는 실현 되 지 않 았 다.예 를 들 어 우리 가 입력 한 요구 에 따라 테스트 사례 를 입력 하지 않 으 면 우 리 는 검색 작업 을 수행 하 는 것 이 아니 라 false 로 돌아 가 야 한다.