โจทย์: กำหนดเมทริกซ์ n×n ที่แถวและคอลัมน์เรียงเพิ่มขึ้น หาองค์ประกอบที่ K น้อยที่สุด (ไม่ใช่ unique)
ตัวอย่าง
Matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
อัลกอริทึม: Binary Search + Count ≤ mid
- Binary search บนช่วงค่า [min, max] ของเมทริกซ์
- สำหรับ mid แต่ละค่า นับจำนวนองค์ประกอบ ≤ mid
- ใช้ property: เริ่มจากมุมขวาบน (i=0, j=n-1) เดินลง-ซ้าย
ตัวอย่างโค้ด Python
class Solution(object):
def kthSmallest(self, matrix, k):
n = len(matrix)
low, high = matrix[0][0], matrix[n-1][n-1]
while low <= high:
mid = low + (high - low) // 2
count = self.count_less_equal(matrix, mid)
if count < k:
low = mid + 1
else:
high = mid - 1
return low
def count_less_equal(self, matrix, target):
"""นับจำนวนองค์ประกอบ ≤ target เริ่มจากมุมขวาบน"""
n = len(matrix)
i, j = 0, n - 1
count = 0
while i < n and j >= 0:
if matrix[i][j] > target:
j -= 1 # เลื่อนซ้าย
else:
count += j + 1 # ทุกตัวในแถวนี้ซ้ายสุดถึง j ≤ target
i += 1 # เลื่อนลง
return count
# ทดสอบ
matrix = [[1,5,9],[10,11,13],[12,13,15]]
ob = Solution()
print(ob.kthSmallest(matrix, 8)) # Output: 13
ตัวอย่าง Input/Output
Input: matrix=[[1,5,9],[10,11,13],[12,13,15]] k=8 Output: 13
ความซับซ้อน: Time O(n log(max-min)), Space O(1) - ดีกว่า Heap O(k log n) เมื่อ k ใหญ่
