โปรแกรมหาดัชนีคอลัมน์ที่มี 1 ตรงสุดซ้ายในเมทริกซ์ไบนารีใน Python

สมมติว่าเรามีเมทริกซ์ไบนารี 2 มิติ แต่ละแถวเรียงลำดับจาก 0 แล้วตามด้วย 1 หาคอลัมน์ที่มี 1 อยู่ไว้สุดซ้าย (ดัชนีน้อยที่สุด) ถ้าไม่มี 1 เลย คืนค่า -1

ตัวอย่าง

เมทริกซ์:

[[0, 0, 0, 1],
 [0, 0, 1, 1],
 [0, 0, 1, 1],
 [0, 0, 1, 0]]

เอาต์พุต: 2 (คอลัมน์ที่ 2 มี 1 อยู่ไว้สุดซ้าย)

ขั้นตอนการแก้ปัญหา

เริ่มจากมุมขวาบน (top-right) เดินไปซ้าย/ล่าง:

1. ถ้าเมทริกซ์ว่าง คืน -1
2. N = จำนวนแถว, M = จำนวนคอลัมน์
3. i = 0, j = M - 1, leftmost = -1
4. วนลูป while i < N and j >= 0:
   • ถ้า matrix[i][j] == 0: i += 1 (ลงไปแถวถัดไป)
   • มิฉะนั้น: leftmost = j, j -= 1 (เดินไปซ้าย)
5. คืนค่า leftmost

การนำไปใช้ใน Python

class Solution:
    def solve(self, matrix):
        if not matrix or not matrix[0]:
            return -1
        N = len(matrix)
        M = len(matrix[0])
        i = 0
        j = M - 1
        leftmost = -1
        while i < N and j >= 0:
            if matrix[i][j] == 0:
                i += 1
            else:
                leftmost = j
                j -= 1
        return leftmost

ob = Solution()
matrix = [
    [0, 0, 0, 1],
    [0, 0, 1, 1],
    [0, 0, 1, 1],
    [0, 0, 1, 0]
]
print(ob.solve(matrix))

อินพุต

[[0, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 0]]

เอาต์พุต

2