C++LeetCode 구현(74.2 차원 행렬 검색)

[LeetCode]74.Search a 2D Matrix 2 차원 행렬 검색
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints:

m == matrix.length

n == matrix[i].length

1 <= m, n <= 100

-104 <= matrix[i][j], target <= 104

이 문 제 는 2 차원 행렬 을 검색 해 야 합 니 다.주어진 행렬 이 질서 가 있 기 때문에 자 연 스 럽 게 2 분 검색 법 을 사용 해 야 한다 고 생각 합 니 다.첫 번 째 열 에서 먼저 2 분 검색 법 으로 목표 값 이 있 는 줄 의 위 치 를 찾 은 다음 에 이 줄 에서 목표 값 이 존재 하 는 지 여 부 를 찾 을 수 있 습 니 다.첫 번 째 2 분 검색 에 있어 서 첫 번 째 열 에 target 값 이 없 을 수 있 기 때문에 어떻게 찾 아야 합 니까?첫 번 째 목표 값 보다 작 지 않 은 수 를 찾 으 면 target 이 첫 번 째 열 에 있 을 때 target 이 있 는 줄 로 돌아 갑 니 다.그러나 target 이 없 으 면 다음 줄 로 돌아 갈 수 있 습 니 다.통일 되 지 않 을 수 있 습 니 다.그래서 첫 번 째 목표 치 보다 큰 수 를 찾 을 수 있 습 니 다.즉,요약 첩 의 세 번 째 유형 입 니 다.그러면 하 나 를 되 돌리 면 반드시 target 이 있 는 줄 입 니 다.그러나 주의해 야 할 것 은 0 으로 돌아 가면 경 계 를 넘 지 않도록 판단 해 야 한 다 는 점 이다.target 이 있 는 줄 수 를 찾 으 면 2 분 검색 을 다시 사용 할 수 있 습 니 다.이 때 는 요약 글 의 첫 번 째 유형 입 니 다.target 값 과 같은 숫자 를 찾 는 것 도 가장 간단 한 유형 입 니 다.분 으로 나 누 어 해결 하면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int left = 0, right = matrix.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrix[mid][0] == target) return true;
            if (matrix[mid][0] < target) left = mid + 1;
            else right = mid;
        }
        int tmp = (right > 0) ? (right - 1) : right;
        left = 0;
        right = matrix[tmp].size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrix[tmp][mid] == target) return true;
            if (matrix[tmp][mid] < target) left = mid + 1;
            else right = mid;
        }
        return false;
    }
};

물론 이 문 제 는 1 차 2 분 검색 법 을 사용 할 수 있 습 니 다.만약 에 우리 가 S 형 에 따라 이 2 차원 배열 을 옮 겨 다 니 면 질서 있 는 1 차원 배열 을 얻 을 수 있 습 니 다.1 차 2 분 검색 법 만 사용 하면 됩 니 다.관건 은 좌표 의 전환 에 있 습 니 다.2 차원 좌표 와 1 차원 좌 표를 어떻게 전환 하 느 냐 가 관건 입 니 다.길이 가 n 인 1 차원 배열 을 m*n 의 2 차원 배열(m*n=n)로 전환 한 후에그러면 원래 1 차원 배열 에서 i 로 표 시 된 요 소 는 2 차원 배열 의[i/n][i%n]위치 에 나타 날 것 입 니 다.이런 점 이 있 으 면 코드 를 잘 쓸 수 있 습 니 다.
해법 2:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size(), n = matrix[0].size();
        int left = 0, right = m * n;
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrix[mid / n][mid % n] == target) return true;
            if (matrix[mid / n][mid % n] < target) left = mid + 1;
            else right = mid;
        }
        return false;
    }
};

이 문 제 는 사실 이분 검색 법 을 사용 하지 않 고 두 바늘 을 직접 사용 해도 된다.i 가 0,j 가 열 수 를 가리 키 면 첫 번 째 로 검 증 된 수 는 2 차원 배열 의 오른쪽 상단 에 있 는 숫자 이다.만약 에 이 숫자 가 target 과 같다 면 true 로 직접 돌아간다.target 보다 크 면 숫자 를 줄 여야 한 다 는 뜻 이 고 열 수 j 는 스스로 1 을 줄인다.target 보다 작 으 면 숫자 를 늘 리 고 줄 수 i 는 1 을 증가 합 니 다.while 순환 이 종료 되 었 지만 target 을 찾 지 못 하면 false 로 돌아 가면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 3:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int i = 0, j = (int)matrix[0].size() - 1;
        while (i < matrix.size() && j >= 0) {
            if (matrix[i][j] == target) return true;
            else if (matrix[i][j] > target) --j;
            else ++i;
        }   
        return false;
    }
};

C++구현 LeetCode(74.2 차원 매트릭스 검색)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 검색 2 차원 매트릭스 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!