2D 정렬 된 배열에서 k smallest \ largest 요소를 찾습니다.

Question

2 차원 배열이 주어졌습니다. 행과 열이 정렬됩니다.

가장 효율적인 방법으로 2 차원 어레이에서 k 번째로 큰 요소를 찾습니다. 제자리에서 할 수 있습니까?

Answer 1

약간의 bruteforce in-place 솔루션 : 이진 검색을 통해 값을 추측 해보십시오. 최대 값과 최소값을 알고 있습니다 (코너에 있음). 모든 후보자에게 더 작은 요소와 더 큰 요소 사이의 경계를 따르는 동안 더 작은 요소의 수를 세십시오. 배열이 소트되기 (위해) 때문에,이 경계는 그것을 통과하는 합리적으로 짧은 패스입니다. 더 작은 요소들 사이에서 최대 값의 위치를 ​​추적하십시오. 이 값은 여러 번 나타날 수 있습니다. 그것들을 센다. N × N 배열을 가정하면, 이것은 O (N * B)를 취할 것입니다. 여기서 B는 값의 비트 수입니다.

나는 큰 소리로 생각하고있다. 나는 믿을 수 없을만큼 최적의 해결책에 대해 읽기를 모호하게 기억하지만, 나는 어디 있는지 모른다.