मान लीजिए हमारे पास एक n x n मैट्रिक्स है जहां प्रत्येक पंक्ति और कॉलम बढ़ते क्रम में क्रमबद्ध हैं, हमें मैट्रिक्स में kवां सबसे छोटा तत्व ढूंढना है। ध्यान दें कि यह क्रमबद्ध क्रम में kवां सबसे छोटा तत्व है, kवां अद्वितीय तत्व नहीं। इसलिए यदि इनपुट [[1,5,9],[10,11,13],[12,13,15]] जैसा है, यदि k = 8, तो आउटपुट 13 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- checkVal() नामक एक मेथड परिभाषित करें और आर्गुमेंट्स मैट्रिक्स और वैल्यू हैं
- i := 0, j := matrix[0] की लंबाई - 1, counter := 0
- जबकि i < मैट्रिक्स की लंबाई और j >= 0
- यदि matrix[i, j] > value, तो j को 1 से घटाएं, अन्यथा counter := counter + j + 1, i को 1 से बढ़ाएं
- counter लौटाएं
- मुख्य विधि इस तरह होगी -
- n := मैट्रिक्स की पंक्ति, high := निचला दायां कोना तत्व, low := ऊपरी बायां कोना तत्व
- जबकि low <= high, करें
- mid = low + (high - low)/2
- count := checkVal(matrix, mid)
- यदि count < k, तो low := mid + 1, अन्यथा high := mid - 1
- low लौटाएं
उदाहरण
class Solution(object):
def kthSmallest(self, matrix, k):
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