找出Python中最小子矩阵的程序
假设我们有一个2D矩阵和另一个值k。我们的目标是返回一个矩阵,其中包含所有kxk子矩阵的最小值。
所以,如果输入像
3 | 5 | 6 |
8 | 6 | 5 |
4 | 3 | 12 |
并且k = 2,
那么输出将是[[3,5],[3,3]]。
从输入中,我们可以看到左上子矩阵的最小值为3
3 58 6
右上方子矩阵的最小值为5
5 66 5
左下子矩阵的最小值为3
8 64 3
右下子矩阵的最小值为3
6 53 12
在线示例
让我们看下面的实现以更好地理解-
import collectionsclass 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