मान लीजिए हमारे पास एक m x n मैट्रिक्स है। हमें उस मैट्रिक्स में एक वैल्यू खोजने के लिए एक कुशल एल्गोरिदम लिखना है। इस मैट्रिक्स में निम्न गुण हैं -
- प्रत्येक पंक्ति में पूर्णांक बाएं से दाएं आरोही क्रम में सॉर्टेड हैं।
- प्रत्येक कॉलम में पूर्णांक ऊपर से नीचे आरोही क्रम में सॉर्टेड हैं।
इसलिए यदि मैट्रिक्स इस तरह है -
| 1 | 4 | 7 | 11 | 15 |
| 2 | 5 | 8 | 12 | 19 |
| 3 | 6 | 9 | 16 | 22 |
| 10 | 13 | 14 | 17 | 24 |
| 18 | 21 | 23 | 26 | 30 |
यदि टारगेट 5 है, तो true लौटाएं, यदि टारगेट 20 है, तो false लौटाएं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- len := कॉलम की संख्या, c1 := 0, c2 := len - 1
- जब तक True
- यदि matrix[c1, c2] = टारगेट, तो true लौटाएं
- अन्यथा यदि matrix[c1, c2] > टारगेट, तो c2 := c2 - 1, जारी रखें
- c1 := c1 + 1
- यदि c1 >= पंक्ति संख्या या c2 < 0, तो false लौटाएं
- false लौटाएं
यह एल्गोरिदम मैट्रिक्स के ऊपरी-दाएं कोने से शुरू होता है और टारगेट के आधार पर बाएं या नीचे जाता है।
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
class Solution:
def searchMatrix(self, matrix, target):
try:
length = len(matrix[0])
counter1, counter2 = 0, length - 1
while True:
if matrix[counter1][counter2] == target:
return True
elif matrix[counter1][counter2] > target:
counter2 -= 1
continue
counter1 = counter1 + 1
if counter1 >= len(matrix) or counter2 < 0:
return False
except:
return False
ob1 = Solution()
print(ob1.searchMatrix([[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], 5))
इनपुट
[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]] 5
आउटपुट
True
