처음 두 개의 큰 숫자의 색인을 찾기위한 함수를 작성하십시오.

Question

온라인 인터뷰 중이 질문을 해결하도록 요청 받았으나 실패했습니다. 나는 즉시 거부 당했다. 알고리즘에 어떤 문제가 있는지 파악하려고합니다.

가장 큰 두 개의 숫자 선택한 프로그래밍 언어에서

정수의 배열을 받아 처음 두 개의 큰 숫자의 인덱스를 반환하는 함수를 작성합니다. 모서리가있는 경우 특수한 행동을 문서화하십시오. 함수의 실행 시간은 O(N)이어야합니다. 여기서 N은 배열의 길이이고 O(1) 추가 공간입니다.

나는 C#에서 숫자 정렬이 방법을 썼다 : 가장자리 경우에 특별한 동작을 문서화로

int[] sortArrayIndicies(int[] numbers) 
{ 
    int high = int.MinValue; 
    int secondHigh = int.MinValue; 

    for(int i = 0; i < numbers.Length; i++) 
    { 
     if (numbers[i] > numbers[high]) 
     { 
     secondHigh = high; 
     high = i; 
     } 
     else if (numbers[i] > numbers[secondHigh]) 
     { 
     secondHigh = i; 
     } 
    } 

    return new[] {high, secondHigh}; 
} 

를, 내가로 응답 한 다음

높은 및 초 숫자가 음수 인 경우 높은 변수가 기본값 0 대신 min int 값으로 초기화되었습니다. 복잡도는 O(N)입니다.

어디서 잘못 되었나요? 나는 전체 목록을 반복하고 있기 때문에 시간 복잡도가 O(N)이라는 것을 안다. 그리고 공간 복잡성은 높고 두 번째 높은 변수를위한 공간의 작은 (고정 된) 양 때문에 O(1)이다.

Answer 1

이 주석은 비 반복 입력에 대해 코드가 충돌 할 것이라는 간접적 인 표현입니다. 초기 반복 중에 numbers[high]이 numbers[int.MinValue]을 참조하는 것과 동일하기 때문입니다.

의견에서 두 값을 0으로 초기화하는 것이 좋습니다. 나는 당신이 더 나아갈 수 있다고 생각하고 두 초기 숫자가 더 큰지에 따라 0과 1 또는 1과 0으로 값을 초기화한다고 생각합니다. 그런 다음 인덱스 2에서 반복 시작합니다. 물론 배열에 적어도 두 개의 요소가 있는지 확인해야합니다.

{1, 2, 5, 3, 4, 5, 4, 3}처럼 두 개의 가장 큰 숫자가 서로 같을 때 프로그램에서 고려해야하는 특별한 경우가 있습니다. 이 경우 high과 secondHigh은 모두 동일한 값을 가지므로 프로그램에서 {2, 5}을 반환해야합니다.