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

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

ดังนั้นหากอินพุตเป็นแบบ

ผลลัพธ์จะเป็น 2 เนื่องจากคอลัมน์ที่สองเหลือ 1 มากที่สุดในเมทริกซ์ทั้งหมด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• หากเมทริกซ์ว่างเปล่า

  • กลับ -1

• N :=จำนวนแถวของเมทริกซ์

• M :=จำนวนคอลัมน์ของเมทริกซ์

• ผม :=0, j :=M - 1

• ซ้ายสุด :=-1

• ในขณะที่ i =0 ทำ

  • ถ้า matrix[i, j] เท่ากับ 0 แล้ว

    • ผม :=ผม + 1

  • มิฉะนั้น

    • ซ้ายสุด :=j

    • เจ :=เจ - 1

• กลับซ้ายสุด

ตัวอย่าง

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