홈>2020-03-18 16:21

java - A에서 N까지 더하는 숫자 쌍 찾기

저는 아마존 소프트웨어 인터뷰 :

Given an integer N and an array of unsorted integers A find all pairs of numbers within A which add up to N

Java로 작동하는 솔루션이 있습니다 :

static void allPairsAddToN(int[] array, int n) {
    for(int c=0;c<array.length; c ++) {
        for(int j=c+1; j<array.length; j++) {
            if(array[c] + array[j] == n)
                System.out.println("(" + array[c] +", " + array[j] +")" );
        }
    }
}

이것이 가장 효율적인 솔루션입니까? 나에게 이것은 \ $O (n ^ 2) \ $에서 실행되는 무차별 대입 방식입니다. 그러나이 문제에 대해 모든 가능성을 고려하지 않아도됩니까 (정렬되지 않은)? 당신이하지 않는 몇 가지 트릭이 있습니까?

답변 # 1
정렬 된n숫자 배열을 가진 경우N에 해당하는 쌍을 찾으려면 O (n) 시간이 걸립니다.

정렬에는 O (n로그n) 시간이 걸립니다.

O (n로그n+n)은 O (n로그n). O (n²)보다 낫습니다. 따라서 배열을 먼저 정렬하는 것이 좋습니다.
답변 # 2
'찾기'의 의미에 따라 달라집니다. 쌍을 세고 싶고 여분의 메모리를 사용하지 않아도되는 경우 하나의 옵션이 있습니다.

정수에서 정수로 빈 해시 맵을 만듭니다. 이것은 우리가 본 각 숫자의 발생 횟수를 저장합니다.

배열의 각 요소 \ $x \ $에 대해지도를 사용하여 \ $N-x \ $의 횟수를 확인하십시오. 그런 다음지도에서 \ $x \ $의 발생 횟수를 늘리십시오.

쿼리와 삽입은 보통 \ $O (1) \ $이므로 \ $O (n) \ $시간에 실행됩니다. 여기서 \ $n \ $는 배열의 길이입니다.

계산하는 대신 쌍을 열거하려면 (예 : 인쇄) 최악의 경우는 모든 쌍의 합계가 \ $N \ $일 때입니다. 예를 들어, 배열은 \ $\ {x, x, x, \ ldots, x \} \ $및 \ $N = 2x \ $입니다.
배열의 길이가 $$n \ $이면 \ $\ binom n2 = \ frac {n (n-1)} {2} = O (n ^ 2) \ $쌍이 있으므로 모든 알고리즘 최악의 경우 적어도 \ $O (n ^ 2) \ $시간이 소요될 것이라고 열거합니다.

Python2.net

java - A에서 N까지 더하는 숫자 쌍 찾기

관련 자료