2 개의 정렬 된 정수 배열을 가지고 있는데, O (logn) 시간에 k 번째로 큰 항목을 찾는 방법은 무엇입니까?

Question

나는 인터뷰에서이 질문을 받았다. O (n) 시간에 분명히 할 수 있었지만 O (logn)에서 해결할 방법을 생각하지 않았습니다. 몇 가지 divide-and-conquer 알고리즘을 사용하는 것처럼 들리지만 잘 모르겠습니다.

Answer 1

둘 다 크기 k로 잘립니다. 필요하다면, 하나 또는 양쪽 배열의 끝에 무한대가 충분히있어 크기 k를 갖도록 프로그램을 작성하게하십시오. 이것은 점근 런타임에 영향을 미치지 않습니다. 실제 구현에서는 좀 더 효율적인 작업을 수행 할 수 있습니다.

그런 다음 각 배열의 k/2 번째 요소를 비교합니다. 요소를 동일하게 비교하면 k 번째 요소를 찾았습니다. 그렇지 않으면, 더 낮은 k/2 번째 요소를 갖는 배열을 A로하고 다른 배열을 B로 놓습니다. A의 아래쪽 절반과 B의 위쪽 절반을 버리고 남은 것의 k/2 번째 요소를 재귀 적으로 찾습니다. k = 1을 명중하면 멈 춥니 다.

모든 단계에서 A의 아래쪽 절반이 너무 작게 보장되고 B의 위쪽 절반이 너무 크게 보장됩니다. 남아있는 k/2 번째 요소는 A의 아래쪽 절반보다 더 크게 보장되므로 원본의 k 번째 요소가 될 것입니다. 파이썬에서 개념의

증명 :

def kth(array1, array2, k): 
    # Basic proof of concept. This doesn't handle a bunch of edge cases 
    # that a real implementation should handle. 
    # Limitations: 
    # Requires numpy arrays for efficient slicing. 
    # Requires k to be a power of 2 
    # Requires array1 and array2 to be of length exactly k 
    if k == 1: 
     return min(array1[0], array2[0]) 
    mid = k//2 - 1 
    if array1[mid] > array2[mid]: 
     array1, array2 = array2, array1 
    return kth(array1[k//2:], array2[:k//2], k//2) 

나는하지만 많은이를 테스트했습니다.