找出Python中最小子矩阵的程序

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

所以,如果输入像

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

在线示例

让我们看下面的实现以更好地理解-

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
输出结果
[[3, 5], [3, 3]]

以上是 找出Python中最小子矩阵的程序 的全部内容, 来源链接: utcz.com/z/356030.html

回到顶部