m * n 의 행렬 에서 어떤 숫자 를 찾 습 니 다.

m * n 의 행렬 에서 어떤 숫자 를 찾 습 니 다.
설명: m * n 의 2 차원 배열 에서 모든 요 소 는 왼쪽 에서 오른쪽으로 증가 하고 위 에서 아래로 증가 합 니 다. 현재 하나의 숫자 를 지정 하여 이 배열 에 이 숫자 가 포함 되 어 있 는 지 확인 합 니 다.예 를 들 어 기 존 매트릭스 matrix 는 다음 과 같다.

[
[1,2,3],
[4,5,6],
[7,8,9]
]

주어진 target = 5, true 주어진 target = 10 을 되 돌려 주 고 false 를 되 돌려 줍 니 다.
해법 1:
체계 적 으로 알고리즘 을 깊이 배 운 적 이 없고 문 제 를 많이 풀 지 않 았 습 니 다. 폭력 을 제거 한 후에 제 가 생각 한 행렬 에서 요소 특성 을 이용 한 해법 은 다음 과 같 습 니 다.

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
       boolean flag = false;
       int maxLength = matrix[0].length;
       for(int i=0;i<matrix.length;i++){
           for(int j=0;j<maxLength;j++){
               if(matrix[i][j] == target){
                   flag = true;
                   break;
               }else if(matrix[i][j]>target){
                   maxLength = j;
                   break;
               }
           }
           if(flag == true){
               break;
           }
       } 
       return flag;
    }
}

해석: 한 줄 한 줄 옮 겨 다 니 며 행렬 요소 간 의 증가 관 계 를 이용 하여 옮 겨 다 니 는 최대 열 수 를 찾 아 순서대로 범 위 를 축소 합 니 다.시간 복잡 도 는 m * n 보다 약간 작다.
해법 2:
이 해법 은 힘 을 다 해 잠 긴 답 해법 이다. 선형 으로 찾 는 방식 이다. 사실 나 는 처음에 이런 해법 을 생각 했 지만 어떻게 for 순환 에 대해 쓰 지 못 했 는 지 대체적으로 분석 한 후에 코드 는 다음 과 같다.

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length;
        int columns = matrix[0].length;
        int row = 0;
        int column = columns-1;
        while(row<=rows-1&&column>=0){//           
            if(matrix[row][column]==target){
                return true;
            }else if(matrix[row][column]>target){
                column--;
            }else{
                row++;
            }
        }
        return false;
    }
}

해석: 행렬 의 오른쪽 상단 을 착안점 으로 하고 목표 값 과 비교 하면 true 로 돌아 갑 니 다. 목표 값 보다 크 면 행렬 의 배열 특성 에 따라 이 열 이 목표 값 보다 크 면 왼쪽으로 이동 합 니 다. 작 으 면 아래로 이동 합 니 다. 여기 서 while 순환 의 판정 은 줄 수가 최대 줄 보다 적 고 열 수가 0 보다 많 음 을 주의 하 십시오.처음에 나 는 왼쪽 상단 을 착안점 으로 삼 아 반복 적 으로 시도 해 보 았 는데 항상 순환 에 들 어가 해결 방법 을 찾 지 못 한 다 는 것 을 알 게 되 었 다.