在二維排序數組中找到k個最小\最大元素

Question

給定一個2維數組。行和列進行排序。

以最有效的方式從二維數組中找到第k個最大的元素。它可以在原地完成嗎？

Answer 1

一個稍微暴力的就地解決方案：嘗試通過二進制搜索來猜測值。你知道最大值和最小值（他們在角落裏）。對於每個候選人，請計算較小元素的數量，同時遵循較小元素和較大元素之間的邊界。由於數組是排序的，因此這個邊界是一條相當短的路徑。跟蹤較小元素中最大的位置。該值可能會出現多次。數它們。假設一個NxN數組，這將需要O（N * B），其中B是值的位數。

我只是在大聲思索......我隱約記得閱讀一個令人難以置信的最佳解決方案，但我不知道在哪裏。