ค้นหา 2D Matrix II ใน Python

สมมติว่าเรามีเมทริกซ์ขนาด m x n หนึ่งตัว เราต้องเขียนอัลกอริธึมที่มีประสิทธิภาพเพื่อค้นหาค่าในเมทริกซ์นั้น เมทริกซ์นี้มีคุณสมบัติดังต่อไปนี้ -

• จำนวนเต็มในแต่ละแถวจะเรียงจากน้อยไปมากจากซ้ายไปขวา
• จำนวนเต็มในแต่ละคอลัมน์จะเรียงลำดับจากน้อยไปมากจากบนลงล่าง

ดังนั้นหากเมทริกซ์เป็นเหมือน −

หากเป้าหมายคือ 5 ให้คืนค่า จริง หากเป้าหมายคือ 20 ให้คืนค่าเท็จ

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

• len :=จำนวนคอลัมน์, c1 :=0, c2 :=len – 1
• ในขณะที่จริง
  • ถ้า matrix[c1, c2] =เป้าหมาย ก็คืนค่า true
  • else if matrix[c1, c2]> target แล้ว c2 :=c2 – 1 ดำเนินการต่อ
  • c1 :=c1 + 1
  • ถ้า c1>=จำนวนแถวหรือ c2 <0 ให้คืนค่าเท็จ
  • คืนค่าเท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

คลาสโซลูชัน:def searchMatrix(self, matrix, target):try:length =len(matrix[0]) counter1, counter2 =0, length-1 while True:if matrix[counter1][counter2] ==target :คืนค่า True elif matrix[counter1][counter2]>target:counter2-=1 ทำต่อ counter1 =counter1 + 1 if counter1>=len(matrix) หรือ counter2<0:return False ยกเว้น:return Falseob1 =Solution()print(ob1 .searchMatrix([[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24 ],[18,21,23,26,30]], 5))

อินพุต

ผลลัพธ์

จริง