สมมติว่าเรามีเมทริกซ์ 2 มิติ โดยที่เมทริกซ์ [r, c] แทนความสูงของคอนโดมิเนียมในเมือง มองเห็นเส้นขอบฟ้าตะวันตก-ตะวันออกโดยใช้ค่าสูงสุดของแต่ละแถวในเมทริกซ์ และสามารถมองเห็นเส้นขอบฟ้าเหนือ-ใต้ได้โดยใช้ค่าสูงสุดของแต่ละคอลัมน์ เราต้องหาเมทริกซ์ใหม่ที่เพิ่มความสูงของคอนโดมิเนียมแต่ละห้องให้สูงที่สุดเท่าที่เป็นไปได้ โดยที่ยังคงเส้นขอบฟ้าตะวันตก-ตะวันออกและเหนือ-ใต้ไว้เหมือนเดิม
ดังนั้นหากอินพุตเป็นแบบ
| 2 | 3 | 4 |
| 5 | 6 | 7 |
| 8 | 9 | 10 |
| 4 | 4 | 4 |
| 7 | 7 | 7 |
| 8 | 9 | 10 |
เนื่องจากเส้นขอบฟ้าทิศตะวันตก-ตะวันออกคือ [4, 7, 10] และเส้นขอบฟ้าเหนือ-ใต้คือ [8, 9, 10] เราสามารถเพิ่มทุกอย่างในแถวแรกให้มีค่า 4 และทุกอย่างในแถวที่สองให้มีค่า 7 โดยไม่ต้องเปลี่ยนเส้นขอบฟ้า
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
r :=รายการสูงสุดของแต่ละแถวในเมทริกซ์
-
c :=รายการสูงสุดของแต่ละคอลัมน์ในเมทริกซ์
-
สำหรับฉันในช่วง 0 ถึงจำนวนแถวของเมทริกซ์ ทำ
-
สำหรับ j ในช่วง 0 ถึงจำนวนคอลัมน์ของเมทริกซ์ ให้ทำ
-
ถ้า r[i]
-
เมทริกซ์[i, j] :=r[i]
-
-
มิฉะนั้น
-
เมทริกซ์[i, j] :=c[j]
-
-
-
-
ส่งคืนเมทริกซ์
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
class Solution: def solve(self, matrix): r = [max(i) for i in matrix] c = [max(i) for i in zip(*matrix)] for i in range(len(matrix)): for j in range(len(matrix[i])): if r[i] < c[j]: matrix[i][j] = r[i] else: matrix[i][j] = c[j] return matrix ob = Solution() matrix = [ [2, 3, 4], [5, 6, 7], [8, 9, 10] ] print(ob.solve(matrix))
อินพุต
[[2, 3, 4], [5, 6, 7], [8, 9, 10]]
ผลลัพธ์
[[4, 4, 4], [7, 7, 7], [8, 9, 10]]
