題目出處
難度
medium
題目分類
Array, Matrix
2026-09-27 一刷
個人範例程式碼 - 一刷 (2026/09/27)
class Solution:
def largestOverlap(self, img1: list[list[int]], img2: list[list[int]]) -> int:
img1_list = []
img2_list = []
# n^2
for i in range(len(img1)):
for j in range(len(img1[0])):
if img1[i][j] == 1:
img1_list.append((i, j))
# n^2
for i in range(len(img2)):
for j in range(len(img2[0])):
if img2[i][j] == 1:
img2_list.append((i, j))
# K1 * K2 (worse = all 1, N^4)
deltas = {}
max_delta = 0
for (i1, j1) in img1_list:
for (i2, j2) in img2_list:
deltas[(i2-i1, j2-j1)] = deltas.get((i2-i1, j2-j1), 0) + 1
if deltas[(i2-i1, j2-j1)] > max_delta:
max_delta = max(max_delta, deltas[(i2-i1, j2-j1)])
return 0 if max_delta == 0 else max_delta
算法說明
主要解題思維如下：
- 先對矩陣降維，排除所有 0 的資訊，只需要專注處理 1 就好。
具體方式為存所有 1 的座標。 - 比較所有的座標並統計，shift 最大值就是最大重疊值（照這組移動會有最大重疊，重疊數量就是統計數量）。
註：如果直接暴力法，比對兩矩陣 （可能在左右上下之類的），那就是必定 O(n^4)，會 TLE，因此需要先降維。
Time Complexity
O(n^2+K1K2)
n^2 掃兩個矩陣
K1K2 對應的是 1 的數量 (worst 就是全 1，為 n^4)
Space Complexity
O(n^2) # 存座標列表 + delta 統計