정렬 된 배열의 모든 쌍 (x, y)을 찾아서 x + y <z

Question

이 질문은 인터뷰 질문입니다. 정렬 된 정수 배열과 숫자 z가 주어지면 배열에서 모든 쌍 (x, y)을 찾아서 x + y가 < z가되도록합니다. O (n^2)보다 더 잘 할 수 있습니까?

P. O (N)에서 모든 쌍 (x, y | x + y == z)을 찾을 수 있다는 것을 압니다.

Answer 1

이 속성이 값 O (N ²) 페어가있을 수 있기 때문에 반드시, (N ²) 시간 O에서 이러한 모든 쌍을 찾을 수 없습니다. 일반적으로 알고리즘은 생성하는 값의 수보다 실행 시간이 적게 걸리지 않습니다.

희망이 도움이됩니다.

Answer 2

생성시 생성 할 수 없습니다. 배열에서 x, y 모두에 대해 x + y < z 인 경우를 생각해보십시오. 세트에있는 n(n - 1)/2 쌍을 모두 터치해야합니다 (예 : 표시). 이것은 근본적으로 O (n^2)입니다.

Answer 3

각 요소가 고유하다는 추가 제한 조건을 추가하면 을 O (N)로 찾을 수 있습니다.

모든 x + y == z 쌍을 찾은 후 해당 조건을 만족하는 모든 x 및 y에 대해 해당 쌍보다 낮은 색인에있는 모든 x 또는 y (하나 선택)가 x + y < 조건.

실제로 이들을 선택하고 출력하면 O (n^2)가되지만 어떤 의미에서는 x + y == z 쌍은 입력과 함께 압축 된 형식의 답입니다.

(각 요소가 고유 한 양식에 대한 입력을 사전에 처리 할 수 ​​있으며 O (N) 시간이 걸립니다.이 솔루션을 정렬되지 않은 배열로 일반화하여 O (nlogn).

시간의 아래에서 쌍을 찾는 것이 솔루션의 크기에 선형으로 비례한다고 말하는 것의 정당화 : 질문은 "0과 주어진 입력 K 사이의 정수는 무엇입니까? ?

Answer 4

해당 속성을 만족하는 모든 쌍을 출력하라는 메시지가 표시되면 출력에 O (N^2) 쌍이있을 수 있으므로 O (N^2)보다 더 좋은 점은 없다고 생각합니다.

그러나 x + y = z에 대해서도 마찬가지입니다. O (N) 솔루션이 있다고 주장하는 경우가 있습니다. 따라서 뭔가 누락되었을 수 있습니다.

원래 질문에 쌍 수를 묻는 것으로 의심됩니다. 이 경우 O (N log (N))로 수행 할 수 있습니다. 각 요소 x에 대해 y = z - x을 찾아 배열에서 y에 대한 이진 검색을 수행하십시오. y의 위치는 x의 해당 특정 값으로 형성 될 수있는 쌍의 수를 제공합니다. 배열의 모든 값을이 값으로 요약하면 대답을 얻을 수 있습니다. 각각에 대해 쌍이 O (log (N)) (2 진 검색)를 취하면 N 개의 값이 있고 그 수를 찾는 것이므로 모든 것이 O (N log (N))입니다. 그것은 분류 정수 배열이기 때문에

Answer 5

, 당신은 이진 검색 알고리즘을 사용할 수 있기 때문에 최고의 O(N)이며, 최악의 평균 경우도 O(N*logN)입니다 O(N*logN)이다.

Answer 6

배열을 정렬 할 수 있고 z보다 작은 모든 요소에 대해 이진 검색 - 총 O (NlogN)을 사용할 수 있습니다.

총 실행 시간 : O (| P | + NlogN). 여기서 P는 결과 쌍입니다.

Answer 7

실제로이 질문에 대한 O (nlogn) 솔루션이 있습니다. 내가 할 수있는 일은 (내가 먼저 할 수 있는지 확인한 후) 내 알고리즘/함수의 출력 형식을 정의하는 것입니다.

나는 이것을 원소들의 시퀀스 (S, T)로 정의 할 것이다. S - 배열에있는 요소의 위치 (또는 그 값)입니다. T - 서브 배열 [0, T]의 위치 예를 들어, T = 3이라면 요소 0, 1, 2 및 3과 결합 된 요소 S가 원하는 조건을 만족한다는 것을 의미합니다.

총 결과는 O (nlogn) 실행 시간 및 O (n) 메모리입니다.