สมมติว่าเรามีเมทริกซ์ขนาด n x n โดยที่แต่ละแถวและคอลัมน์ถูกจัดเรียงตามลำดับที่เพิ่มขึ้น เราต้องหาองค์ประกอบที่เล็กที่สุดที่ k ในเมทริกซ์ โปรดทราบว่ามันเป็นองค์ประกอบที่เล็กที่สุดลำดับที่ k ในลำดับการจัดเรียง ไม่ใช่องค์ประกอบเฉพาะลำดับที่ k ดังนั้นหากอินพุตเป็น [[1,5,9],[10,11,13],[12,13,15]] หาก k =8 ผลลัพธ์จะเป็น 13
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดวิธีหนึ่งที่เรียกว่า checkVal() และอาร์กิวเมนต์คือเมทริกซ์และค่า
- i :=0, j :=ความยาวของเมทริกซ์[0] – 1, ตัวนับ :=0
- ในขณะที่ i <ความยาวของเมทริกซ์และ j>=0
- ถ้าค่า matrix[i, j]> แล้วลด j ลง 1 มิฉะนั้น ตัวนับ :=ตัวนับ + j + 1 ให้เพิ่ม i ขึ้น 1
- เคาน์เตอร์คืนสินค้า
- วิธีหลักจะเป็นเช่น −
- n :=แถวของเมทริกซ์ สูง :=องค์ประกอบมุมขวาล่าง ต่ำ :=องค์ประกอบมุมบนซ้าย
- ในขณะที่ต่ำ <=สูง ทำ
- กลาง =ต่ำ + (สูง – ต่ำ)/2
- จำนวน :=checkVal(เมทริกซ์ กลาง)
- ถ้านับ
- ผลตอบแทนต่ำ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object): def kthSmallest(self, matrix, k): """ :type matrix: List[List[int]] :type k: int :rtype: int """ n = len(matrix) high = matrix[n-1][n-1] low = matrix[0][0] while low<=high: mid = low + (high - low) /2 count = self.check_value(matrix,mid) if count< k: low = mid+1 else : high = mid-1 return int(low) def check_value(self, matrix, value): i = 0 j = len(matrix[0])-1 counter = 0 while(i<len(matrix) and j >=0): if matrix[i][j] > value: j-=1 else: counter+=j+1 i+=1 return counter matrix = [[1,5,9],[10,11,13],[12,13,15]] ob = Solution() print(ob.kthSmallest(matrix, 8))
อินพุต
matrix =[[1,5,9],[10,11,13],[12,13,15]] k = 8
ผลลัพธ์
13
