ধরুন আমাদের একটি n x n ম্যাট্রিক্স রয়েছে যেখানে প্রতিটি সারি এবং কলাম ক্রমবর্ধমান ক্রমে সাজানো হয়েছে, আমাদের ম্যাট্রিক্সের kth ক্ষুদ্রতম উপাদানটি খুঁজে বের করতে হবে। মনে রাখবেন এটি সাজানো ক্রমে kth ক্ষুদ্রতম উপাদান, kth অনন্য উপাদান নয়। সুতরাং ইনপুট যদি হয় [[1,5,9],[10,11,13],[12,13,15]], যদি k =8 হয়, তাহলে আউটপুট হবে 13।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- চেকভাল() নামে একটি পদ্ধতি সংজ্ঞায়িত করুন এবং আর্গুমেন্ট হল ম্যাট্রিক্স এবং মান
- i :=0, j :=ম্যাট্রিক্সের দৈর্ঘ্য[0] – 1, কাউন্টার :=0
- যখন i <ম্যাট্রিক্সের দৈর্ঘ্য এবং j>=0
- যদি ম্যাট্রিক্স[i, j]> মান হয়, তাহলে j 1 দ্বারা হ্রাস করুন, অন্যথায় counter :=counter + j + 1, i 1 দ্বারা বাড়ান
- রিটার্ন কাউন্টার
- প্রধান পদ্ধতি হবে − এর মত
- n :=ম্যাট্রিক্সের সারি, উচ্চ :=নীচে ডান কোণার উপাদান, নিম্ন :=উপরের বাম কোণার উপাদান
- যখন কম <=উচ্চ, কর
- মধ্য =নিম্ন + (উচ্চ - নিম্ন)/2
- গণনা :=চেকভাল(ম্যাট্রিক্স, মিড)
- যদি গণনা
- কম রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
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
