行和列排序矩阵中的k个最小元素

Question

在行和列排序元素中查找kth最小元素：

例子:矩阵划<矩阵row+1矩阵划<矩阵划 mat= 1 2 21 11 23 25 31 36 41

我编写了以下代码，如何提高可读性并提高其复杂性：

import heapq
def kth_smallest(k, mat):
    m = len(mat)
    n = len(mat[0])
    hp = []
    for i in xrange(n):
           heapq.heappush(hp,[mat[0][i], 0, i])
    heapq.heapify(hp)
    while k >1:
        x = heapq.heappop(hp)
        if x[1]+1 < m:
            heapq.heappush(hp,[mat[x[1]+1][x[2]], x[1]+1, x[2]])           
        heapq.heapify(hp)
        k-=1

    return hp[0][0]


print kth_smallest(8, [[1,10,12],[2,11,21], [3,31,45]])

Answer 1

一个非常简单的方法是希望列表添加和标准Python排序是快速的(后者对于部分排序的数组尤其快速)。

在这种情况下，您可以使用sum函数的第二个参数作为和的起点，并使用：

def kth_smallest(k, mat):
    entries = sorted(sum(mat, []))
    return entries[k - 1]

在我的机器上，给出的例子是，对于小矩阵，这比您的解决方案要好，但是对于较大的矩阵，则会分解。然而，理解起来要容易得多。

+----+---------------------------------------+----------+---------+--------------+
| k  |                matrix                 | Graipher | Harsha  | Janne Karila |
+----+---------------------------------------+----------+---------+--------------+
|  1 | [[1,10,12],[2,11,21], [3,31,45]]      | 1.34 µs  | 1.61 µs | 1.07 µs      |
|  8 | [[1,10,12],[2,11,21], [3,31,45]]      | 1.22 µs  | 5.94 µs | 3.72 µs      |
|  8 | [[1,10,12, 25, 38, 42, 51],           | 2.43 µs  | 12 µs   | 5.55 µs      |
|    | [2,11,21, 35, 48, 52, 67],            |          |         |              |
|    | [3,31,45, 47, 58, 63, 72],            |          |         |              |
|    | [4, 32, 46, 48, 59, 64, 73]]          |          |         |              |
| 25 | [range(i, i+50) for i in range(50)]   | 286 µs   | 220 µs  | 42.4 µs      |
| 25 | [range(i, i+100) for i in range(100)] | 1.8 ms   | 455 µs  | 79.3 µs      |
+----+---------------------------------------+----------+---------+--------------+

就风格而言，只有少数几个违反PEP8的地方，所有操作人员周围都缺少空格.