Python查找最小子矩阵的程序
假设我们有一个二维矩阵和另一个值k。我们的目标是返回一个矩阵,其中包含所有k x k子矩阵的最小值。
因此,如果输入类似于
3 | 5 | 6 |
8 | 6 | 5 |
4 | 3 | 12 |
并且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]]