โจทย์: นับจำนวนจำนวนเต็มลบใน Matrix ที่เรียงลำดับจากน้อยไปมากทั้งแถวและคอลัมน์ (Row-wise และ Column-wise sorted)
เงื่อนไข Matrix ที่เรียงแล้ว
ค่าทุกตำแหน่ง จะน้อยกว่าหรือเท่ากับค่าทางขวา (คอลัมน์ถัดไป) และค่าด้านล่าง (แถวถัดไป)
M = [[-40, -12, 1, 5],
[-20, -2, 5, 15],
[-22, -1, 13, 18],
[-12, 0, 15, 38]]อัลกอริทึมที่เหมาะสม (O(m+n))
เริ่มจากมุมซ้ายล่าง (หรือขวาบน) แล้วเคลื่อนที่ตามเงื่อนไข:
- ถ้าค่าปัจจุบัน >= 0: ขึ้นบน 1 แถว (ค่าจะน้อยลง)
- ถ้าค่าปัจจุบัน < 0: นับแล้วขยับขวา 1 คอลัมน์
matrix = [
[-40, -12, 1, 5],
[-20, -2, 5, 15],
[-22, -1, 13, 18],
[-12, 0, 15, 38]
]
row_count = len(matrix)
col_count = len(matrix[0])
row = row_count - 1 # เริ่มแถวสุดท้าย
col = 0 # เริ่มคอลัมน์แรก
count = 0
while row >= 0 and col < col_count:
if matrix[row][col] >= 0:
row -= 1 # ขึ้นบน
else:
count += (row + 1) # ทุกแถวเหนือคอลัมน์นี้ต้องเป็นลบด้วย
col += 1 # ขยับขวา
print("Count of Negative Integers:", count) # 7ผลลัพธ์
Count of Negative Integers: 7เหตุผลที่ทำงานได้
เพราะ Matrix เรียงแล้ว: หาก M[row][col] < 0 แล้ว ทุกแถวเหนือ (0 ถึง row) ในคอลัมน์เดียวกันก็ต้องเป็นลบเช่นกัน จึงนับได้ทีละ (row+1) ทันที
ประยุกต์ใช้
อัลกอริทึมเดียวกันใช้ได้กับการนับค่าที่ น้อยกว่าค่าใดก็ได้ (ไม่ใช่แค่ 0) โดยเปลี่ยนเงื่อนไข >= 0 เป็น > threshold
