একটি n x n ম্যাট্রিক্স দেওয়া আছে যেখানে প্রতিটি রো এবং কলাম ইনক্রিজিং অর্ডারে সর্টেড। ম্যাট্রিক্সে k-তম স্মলেস্ট এলিমেন্ট বের করতে হবে (ইউনিক এলিমেন্ট নয়, সর্টেড অর্ডারে k-তম)।
ইনপুট [[1,5,9],[10,11,13],[12,13,15]], k = 8 হলে আউটপুট 13।
সমাধানের ধাপসমূহ
- checkVal() মেথড ডিফাইন করুন (matrix, value আর্গুমেন্ট):
- i := 0, j := len(matrix[0])-1, counter := 0
- যখন i < len(matrix) এবং j >= 0:
- যদি matrix[i][j] > value: j--, অন্যথায় counter += j+1, i++
- counter রিটার্ন
- মূল মেথড:
- n := matrix রো, 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
