Python查找最小子矩阵的程序


假设我们有一个二维矩阵和另一个值k。我们的目标是返回一个矩阵,其中包含所有k x k子矩阵的最小值。

因此,如果输入类似于

356
865
4312

并且k = 2,

则输出将为[[3, 5], [3, 3]]。

从输入中,我们可以看到左上角子矩阵的最小值为3

3 5
8 6

右上角子矩阵的最小值为5

5 6
6 5

左下角子矩阵的最小值为3

8 6
4 3

右下角子矩阵的最小值为3

6 5
3 12

为了解决这个问题,我们将遵循以下步骤:

  • 对于每个行索引r和矩阵中的行项目,执行以下操作:

    • q := 一个新的双端队列

    • nrow := 一个新的列表

    • 对于范围从0到行大小的i,执行以下操作:

      • 如果q不为空且q[0]等于i - k,则

        • 弹出q中最左边的项

      • 当q不为空且row[q[-1]] > row[i]不为零时,执行以下操作:

        • 弹出q中最右边的项

      • 在q的右端插入i

      • 在nrow的末尾插入row[q[0]]

    • matrix[r] := nrow

  • 对于范围从0到matrix[0]大小的j,执行以下操作:

    • q := 一个新的双端队列

    • ncol := 一个新的列表

    • 对于范围从0到矩阵大小的i,执行以下操作:

      • 如果q不为空且q[0]等于i - k,则

        • 弹出q中最左边的项

      • 当q不为空且matrix[q[-1]][j] > matrix[i][j]不为零时,执行以下操作:

        • 弹出q中最右边的项

      • 在q的右端插入i

      • 在ncol的末尾插入matrix[q[0]][j]

      • 对于范围从0到矩阵大小的i,执行以下操作:

        • matrix[i][j] := ncol[i]

  • ret := 一个大小为matrix - k + 1的新列表,初始化为0

  • 对于范围从0到ret大小的i,执行以下操作:

    • 对于范围从0到ret[0]大小的j,执行以下操作:

      • ret[i][j] := matrix[i + k - 1][j + k - 1]

  • 返回ret

示例

让我们看看下面的实现,以便更好地理解:

在线演示

import collections
class Solution:
   def solve(self, matrix, k):
      for r, row in enumerate(matrix):
         q = collections.deque()
         nrow = []
         for i in range(len(row)):
            if q and q[0] == i - k:
               q.popleft()
            while q and row[q[-1]] > row[i]:
               q.pop()
            q.append(i)
            nrow.append(row[q[0]])
         matrix[r] = nrow
      for j in range(len(matrix[0])):
         q = collections.deque()
         ncol = []
         for i in range(len(matrix)):
            if q and q[0] == i - k:
               q.popleft()
            while q and matrix[q[-1]][j] > matrix[i][j]:
               q.pop()
            q.append(i)
            ncol.append(matrix[q[0]][j])
         for i in range(len(matrix)):
            matrix[i][j] = ncol[i]
      ret = [[0] * (len(matrix[0]) - k + 1) for _ in range(len(matrix) - k + 1)]
      for i in range(len(ret)):
         for j in range(len(ret[0])):
            ret[i][j] = matrix[i + k - 1][j + k - 1]
         return ret
ob = Solution()
print(ob.solve(matrix = [
   [3, 5, 6],
   [8, 6, 5],
   [4, 3, 12]
], k = 2))

输入

[[3, 5, 6],[8, 6, 5],[4, 3, 12]], 2

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

[[3, 5], [3, 3]]

更新于:2020年12月23日

220 次查看

启动你的职业生涯

通过完成课程获得认证

开始
广告