1

按行和列排序的矩阵。我们需要Kth从给定的矩阵中找到最小的元素。

有一个时间复杂度的解决方案，O(KlogM)但需要一个线性时间算法来解决这个问题。

示例矩阵： 

1   3    5
2   4    6
7   8    9

假设 M=no of rows, N=no of columns and M<N。

我的解决方案：

  1. matrix[i][0]通过获取所有元素创建大小为 M 的堆。
  2. 找到最小的元素并从相应的行中推送下一个元素。
  3. 重复第二步，直到找到Kth最小的。
4

2 回答 2

4

Frederickson and Johnson 算法的工作原理大致如下。（它总是让我想起Quickselect。）这是来自使用不同实现作为模板的实现，因此细节可能与他们的论文中的有所不同，但它具有相同的时间复杂度和相同的想法。我假设krun from 0to的合法值M * N - 1。

我们将访问i第 th 行和j第 th 列中的元素作为A[i, j]（从 0 开始计数）。此外，我们将假设我们可以访问A[i, -1]哪个是负无穷大，A[i, N]哪个是正无穷大。我们维护两个索引数组left[0 .. M)和right[0..M)，以及两个变量lessthanleft和greaterthanright，具有以下属性：

  • 存在一个矩阵元素A[i0, j0]，因此对于所有行i，我们都有A[i, left[i] - 1] < A[i0, j0] <= A[i, left[i]]。也就是说，如果它在 row 中，left[i]大致是该位置。A[i0, j0]i
  • 从到的值之left[i]和是。请注意，是由 表示的位置左侧的位置中的矩阵元素的数量- 即严格小于 的矩阵元素。i0M - 1lessthanleftlessthanleftleftA[i0, j0]
  • lessthanleft <= k. 所以这表示我们正在寻找的元素i在left[i].
  • 存在一个矩阵元素A[i1, j1]，因此对于所有行i，我们都有A[i, right[i] - 1] < A[i1, j1] <= A[i, right[i]]。也就是说，如果它在 row 中，right[i]大致是该位置。A[i1, j1]i
  • 从到的值之N - right[i]和是。请注意，是由 表示的位置右侧的位置中的矩阵元素的数量- 即严格大于 的矩阵元素。i0M - 1greaterthanrightgreaterthanrightrightA[i1, j1]
  • greaterthanright <= M * N - k. 所以这表示我们正在寻找的元素i在right[i].

这些属性可以通过设置 to 的每个元素、 to 的每个元素以及两者来初始化-left除非0（在这种right情况下我们 return ）或（在这种情况下我们 return ）。顺便说一下，这对应于, , , 。Nlessthanleftgreaterthanright0k = 0A[0, 0]k = M*N - 1A[M-1, N-1]i0=0j0=0i1=M-1j1=N-1

现在在每次迭代中，我们选择一个带有 的枢轴矩阵A[i2, j2]元素left[i2] <= j2 < right[i2]。（有几种策略；我将在下面讨论。）我们使用数组less[0..M)，lessequal[0..M)我们将填充下面的内部循环，并设置变量nlessandnequal和ngreaterto 0。在内部循环中，我们遍历所有 rows i，并设置less[i]and lessequal[i]，这样A[i, less[i] - 1] < A[i2, j2] <= A[i, less[i]]and A[i, lessequal[i] - 1] <= A[i2, j2] < A[i, lessequal[i]]。（因为less[i-1] >= less[i]，您可以使用 和 的值less[i-1]并lessequal[i-1]从那里开始向左线性搜索，以使这O(N)总体上花费时间。）在我们添加到 的每个这样的步骤之后，我们添加less[i] - left[i]到，然后我们添加到。nlesslessequal[i] - less[i]nequalright[i] - lessequal[i]ngreater

在这个内部循环之后，我们检查是否lessthanleft + nless >= k。如果是这种情况，我们A[i2, j2]通过设置right为 be less（如果要防止在循环中为数组分配，或通过将值从lessto复制值，通过指针翻转right）和greaterthanrightto继续处理条目greaterthanright + ngreater + nequal，并继续下一个迭代。如果，那么我们通过设置为 be和to belessthanleft + nless + nequal < k继续处理大于的条目，并继续下一次迭代。否则，我们要查找的条目在等于 的条目中，所以我们返回。A[i2, j2]leftlessequallessthanleftlessthanleft + nless + nequalA[i2, j2]A[i2, j2]

现在关于选择支点。一种方法是c在区间中选择一个随机数[0 .. N * M - lessthanleft - greaterthanright)；然后我们找到包含和c之间的第 th 个矩阵元素的行，方法是从每个开始，直到它变为负数。现在选择它变成负数的地方并让。或者，您可以对每行中剩余条目的中位数进行中位数样式计算。leftrightleft[i] - right[i]ci0ij = round((left[i] + right[i])/2)

所以一般来说，每行之间left[i]和right[i]每行上的矩阵元素集都会被拆分，希望在每次迭代中大致分成两半。复杂性分析类似于快速选择分析，其中预期的迭代次数“几乎可以肯定”（在数学意义上）与初始池中的值数量成对数。通过使用中位数风格的枢轴选择，我相信您可以确定地实现这一点，同时在实际运行时支付它，但我现在假设“几乎可以肯定”就足够了。（这与快速排序为 O(N lg(N)) 的条件相同。）任何单独的迭代都需要O(M)时间来选择一个枢轴，然后O(N)是内部循环中的时间。最初的候选人库有M*N成员，所以迭代次数几乎肯定是O(lg(M * N)) = O(lg(M) + lg(M))，总复杂度为O(N * (lg(M) + lg(N))). 使用每个行都有一个条目的堆的算法需要O(k * lg(M))，这要糟糕得多，因为k只有 有界N*M。

这是一个简单的例子：考虑M=4, N=5，我们需要k=11从给出的矩阵中挑选出第 th 个元素，A如下所示：

 6 12 17 17 25
 9 15 17 19 30
16 17 23 29 32
23 29 35 35 39

我们初始化left到[0,0,0,0]，right到[5,5,5,5]，lessthanleft和greaterthanright两者都到0。

假设我们选择第一次迭代A[1, 2]=17作为枢轴。在内部循环中，我们开始检查从 entryright[0]-1=4到左侧的第一行，找到一个最多为 的数字的第一次出现17。这是在列中3，所以我们设置lessequal[0]=3+1=4。我们现在继续搜索严格小于的数字的第一次出现17；这发生在列中1，所以我们设置less[0]=1+1=2. 对于下一行，我们可以开始寻找一个最多17位于 column的值，并在 column so setlessequal[0]中找到它。寻找一个严格小于start from的值，我们设置. 继续我们得到和。因此, , 和2lessequal[1]=2+1=317less[0]less[1] = 2less = [2,2,1,0]lessequal = [4,3,2,0]nless = 5nequal = 4ngreater = 11. 我们有lessthanleft + nless + nequal = 9 < 11，所以我们继续使用大于17和设置的条目left = lessequal = [4,3,2,0]和lessthanleft = 9。

对于下一次迭代，我们需要在和i之间的中心某行上选择一个枢轴。也许我们选择了行，这意味着我们有。在内部循环中，我们现在得到and和and 。现在，我们继续使用小于和设置的条目和。left[i]right[i]2A[2,3] = 29less = [5,4,3,1]lessequal = [5,4,4,2]nless = 4nequal = 2ngreater = 5lessthanleft + nless = 13 > 1129right = less = [5,4,3,1]greaterthanright = 7

对于第三次迭代，现在每一行只剩下一个条目。我们随机选择一行 - 也许是 row 3。枢轴是A[3,0] = 23。在内部循环中，我们得到less = [4,4,2,0]和lessequal = [4,4,3,1]。因此nless = 1,nequal = 2和ngreater = 1。我们现在有lessthanleft + nless = 10 < k = 11 <= lessthanleft + nless + nequal = 12，所以我们返回23。实际上，有 10 个矩阵条目严格小于23（A[i, less[i]]上次迭代左侧的那些）和最多 12 个矩阵条目23（上次迭代左侧的那些A[i, lessequal[i]]）。

于 2013-09-26T20:29:44.947 回答
-1

我认为您可以编写一种O(k)算法，从当前最小值“跳转”到下一个最小值，从而进行最多k操作。您可以为此使用 2 个引用，一个指示所有列的当前最小值，一个指示所有行的当前最小值。然后，您可以按行或按列在每次迭代中前进。在 k 次迭代之后，您将获得所需的Kth值。

于 2013-09-26T13:34:44.537 回答