在二维数组上找到第K个最小元素(或中位数)的最快算法? [英] Fastest algorithm for Kth smallest Element (or median) finding on 2 Dimensional Array?

问题描述

我在相关主题上看到了很多SO主题，但是没有一个主题提供了有效的方法.

我想在2D数组 [1..M] [1..N] 上找到第 k个最小元素(或中位数)，其中每一行是升序排列，所有元素都是不同的.

我认为有 O(M log MN)解决方案，但是我不知道实现的方法.(中位数的中位数或使用具有线性复杂度的分区是一种方法，但现在不知道了...).

这是一个古老的Google面试问题，可以在此处进行搜索./p>

但是现在我要提示或描述最有效的算法(最快一种).

我还在此处，但我不明白.

更新1:在这里找到了一个解决方案，但是在确定尺寸时很奇怪.

解决方案

已添加了另一个答案以提供实际的解决方案.由于评论中有很多兔子洞，因此保留了这一条.

---

我相信最快的解决方案是k路合并算法.这是一种 O(N log K)算法，用于将具有全部 N 个项目的 K 个排序列表合并为一个大小 N .

https://en.wikipedia.org/wiki/K-way_merge_algorithm#k-way_merge

给出一个 MxN 列表.最终为 O(MNlog(M)).但是，这是对整个列表进行排序.由于您只需要前最小的 K 个项目，而不是所有的 N * M ，因此性能为 O(Klog(M)).假设 O(K)< = O(M).这比您要查找的要好得多.

尽管这假设您有 N 个大小为 M 的排序列表.如果您实际上具有大小为 N 的 M 个排序列表，则可以通过更改数据循环方式(参见下面的伪代码)来轻松处理(尽管确实如此)表示性能是 O(K log(N)).

k向合并仅通过插入 O(log N)和 O(log N)找寻思路.

用于k路合并的伪代码看起来像这样:

1. 对于每个排序的列表，请使用某种确定值来自哪个列表的方法将第一个值插入数据结构.IE:您可以在数据结构中插入 [value，row_index，col_index] ，而不只是 value .这也使您可以轻松地处理列或行上的循环.
2. 从数据结构中删除最低值，并将其追加到排序后的列表中.
3. 鉴于步骤#2中的项来自列表 I ，请将列表 I 中的下一个最小值添加到数据结构中.IE:如果值是第5行col 4(data [5] [4]).然后，如果将行用作列表，则下一个值将是行5列5(data [5] [5]).如果使用的是列，则下一个值为行6列4(data [6] [4]).像#1一样，将下一个值插入数据结构中(即: [value，row_index，col_index] )
4. 根据需要返回步骤2.

根据您的需要，执行2-4次 K 次.

I see a lot of SO topics on related topics but none of them provides the efficient way.

I want to find the k-th smallest element (or median) on 2D array [1..M][1..N] where each row is sorted in ascending order and all elements are distinct.

I think there is O(M log MN) solution, but I have no idea about implementation. (Median of Medians or Using Partition with Linear Complexity is some method but no idea any more...).

This is an old Google interview question and can be searched on Here.

But now I want hint or describe the most efficient algorithm (the fastest one).

Also I read a paper on here but I don't understand it.

Update 1: one solution is found here but when dimension is odd.

解决方案

Another answer has been added to provide an actual solution. This one has been left as it was due to quite the rabbit hole in the comments.

---

I believe the fastest solution for this is the k-way merge algorithm. It is a O(N log K) algorithm to merge K sorted lists with a total of N items into a single sorted list of size N.

https://en.wikipedia.org/wiki/K-way_merge_algorithm#k-way_merge

Given a MxN list. This ends up being O(MNlog(M)). However, that is for sorting the entire list. Since you only need the first K smallest items instead of all N*M, the performance is O(Klog(M)). This is quite a bit better than what you are looking for, assuming O(K) <= O(M).

Though this assumes you have N sorted lists of size M. If you actually have M sorted lists of size N, this can be easily handled though just by changing how you loop over the data (see the pseudocode below), though it does mean the performance is O(K log(N)) instead.

A k-way merge just adds the first item of each list to a heap or other data structure with a O(log N) insert and O(log N) find-mind.

Pseudocode for k-way merge looks a bit like this:

1. For each sorted list, insert the first value into the data structure with some means of determining which list the value came from. IE: You might insert [value, row_index, col_index] into the data structure instead of just value. This also lets you easily handle looping over either columns or rows.
2. Remove the lowest value from the data structure and append to the sorted list.
3. Given that the item in step #2 came from list I add the next lowest value from list I to the data structure. IE: if value was row 5 col 4 (data[5][4]). Then if you are using rows as lists, then the next value would be row 5 col 5 (data[5][5]). If you are using columns then the next value is row 6 col 4 (data[6][4]). Insert this next value into the data structure like you did #1 (ie: [value, row_index, col_index])
4. Go back to step 2 as needed.

For your needs, do steps 2-4 K times.

这篇关于在二维数组上找到第K个最小元素(或中位数)的最快算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！