สมมติว่าเรามีเมทริกซ์ไบนารี เราต้องหาจำนวนองค์ประกอบในเมทริกซ์ที่เป็นไปตามกฎต่อไปนี้ -
-
เมทริกซ์[r, c] =1
-
matrix[r, j] =0 สำหรับทุก ๆ j เมื่อ j ไม่เท่ากับ c และ matrix[i, c] =0 สำหรับทุก ๆ i เมื่อ i ไม่เท่ากับ r
ดังนั้นหากอินพุตเป็นแบบ
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
ผลลัพธ์จะเป็น 3 เนื่องจากเรามีเซลล์ (0,2) (1,0) และ (2,1) ที่ตรงตามเกณฑ์
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
หากเมทริกซ์ว่างเปล่า
-
คืนค่า 0
-
-
row :=รายการผลรวมของรายการแถวทั้งหมดในเมทริกซ์
-
col :=รายการผลรวมของรายการคอลัมน์ทั้งหมดในเมทริกซ์
-
m :=จำนวนแถวของเมทริกซ์
-
n :=จำนวนคอลัมน์ของเมทริกซ์
-
res :=0
-
สำหรับ r ในช่วง 0 ถึง m - 1 ให้ทำ
-
สำหรับ c ในช่วง 0 ถึง n - 1 ทำ
-
ถ้า matrix[r, c] คือ 1 และ row[r] คือ 1 และ col[c] เป็น 1 ด้วย ดังนั้น
-
res :=res + 1
-
-
-
-
ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(matrix):
if not matrix:
return 0
row = [sum(r) for r in matrix]
col = [sum(c) for c in zip(*matrix)]
m, n = len(matrix), len(matrix[0])
res = 0
for r in range(m):
for c in range(n):
if matrix[r][c] == 1 and row[r] == 1 and col[c] == 1:
res += 1
return res
matrix = [
[0, 0, 1],
[1, 0, 0],
[0, 1, 0]
]
print(solve(matrix)) อินพุต
[[0, 0, 1],[1, 0, 0],[0, 1, 0]]
ผลลัพธ์
3
