Python에서 2D Matrix II 검색

하나의 m x n 행렬이 있다고 가정합니다. 우리는 그 행렬에서 값을 찾는 효율적인 알고리즘을 작성해야 합니다. 이 행렬에는 다음과 같은 속성이 있습니다. -

• 각 행의 정수는 왼쪽에서 오른쪽으로 오름차순으로 정렬됩니다.
• 각 열의 정수는 위에서 아래로 오름차순으로 정렬됩니다.

따라서 행렬이 다음과 같은 경우 -

target이 5이면 true를 반환하고 target이 20이면 false를 반환

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• len :=열 수, c1 :=0, c2 :=len – 1
• 사실일 때
  • matrix[c1, c2] =target이면 true를 반환합니다.
  • else if matrix[c1, c2]> target, then c2 :=c2 – 1, 계속
  • c1 :=c1 + 1
  • c1>=행 개수 또는 c2 <0이면 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