資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學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
輸出
[[3, 5], [3, 3]]
220 次檢視
