LeetCode - 2D 매트릭스 검색

문제 설명



m x n 정수 행렬 행렬에서 값 대상을 검색하는 효율적인 알고리즘을 작성합니다. 이 행렬에는 다음과 같은 속성이 있습니다.
  • 각 행의 정수가 왼쪽에서 오른쪽으로 정렬됩니다.
  • 각 행의 첫 번째 정수가 이전 행의 마지막 정수보다 큽니다.

  • 문제 진술 출처: https://leetcode.com/problems/search-a-2d-matrix

    예 1:



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


    예 2:



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


    제약:

    - m == matrix.length
    - n == matrix[i].length
    - 1 <= m, n <= 100
    - -10^4 <= matrix[i][j], target <= 10^4
    


    설명



    무차별 대입 방식



    순진한 접근 방식은 매트릭스를 탐색하고 대상을 하나씩 검색하는 것입니다. 중첩된 for 루프를 실행하고 대상이 있는 모든 요소를 ​​확인합니다. 대상 요소를 찾으면 true 또는 false를 반환합니다.

    이 접근 방식의 C++ 스니펫은 다음과 같습니다.

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(matrix[i][j] == target) {
                return true;
            }
        }
    }
    
    return false;
    


    위 접근 방식의 시간 복잡도는 O(N^2)입니다.

    이진 검색



    문제 설명에 따라 각 행의 행렬 요소는 왼쪽에서 오른쪽으로 정렬됩니다. 따라서 이진 검색을 연속으로 쉽게 사용할 수 있습니다.

    그러나 요소를 검색하는 데 필요한 행을 어떻게 찾을 수 있습니까? 행렬이 전달하는 또 다른 속성은 각 행의 모든 ​​첫 번째 정수가 이전 행의 마지막 요소보다 크다는 것입니다. 즉, 열도 위에서 아래로 정렬됩니다. 첫 번째 열에 이진 검색을 적용합니다.

    먼저 알고리즘을 확인해 봅시다.

    // searchMatrix function
    - set l = 0, m = matrix.size, n = matrix[0].size
          r = m - 1
          int mid
    
    - loop while l <= r
      - set mid = l + (r - l) / 2
    
    // if the element is present in the middle row of the matrix
    // we execute a binary search in the middle row
      - if target >= matrix[mid][0] && matrix[mid][n - 1]
        - return binarySearch(matrix[mid], n, target)
    
      - if target < matrix[mid][0]
        - set r = mid - 1
      - else
        - set l = mid + 1
    - while loop end
    
    - return false
    
    // binarySearch function
    - set l = 0, r = n - 1
      int mid
    
    - loop while l <= r
      - set mid = l + (r - l) / 2
    
      - if row[mid] == target
        - return true
    
      - if target < row[mid]
        - set r = mid - 1
      - else
        - set l = mid + 1
    
    - while loop end
    
    - return false
    


    이 함수의 시간 복잡도는 O(log(n) + log(m))이고 공간 복잡도는 O(1)입니다. n은 열의 수이고 m은 행렬의 행 수입니다.

    C++, Golang 및 Javascript에서 솔루션을 확인합시다.

    C++ 솔루션




    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int l = 0, m = matrix.size(), n = matrix[0].size();
            int r = m - 1;
            int mid;
    
            while(l <= r) {
                mid = l + (r - l) / 2;
    
                if(target >= matrix[mid][0] && target <= matrix[mid][n - 1]) {
                    return binarySearch(matrix[mid], n, target);
                }
    
                if(target < matrix[mid][0]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
    
            return false;
        }
    
        bool binarySearch(vector<int>& row, int n, int target) {
            int l = 0, r = n - 1;
            int mid;
    
            while(l <= r) {
                mid = l + (r - l) / 2;
    
                if(row[mid] == target) {
                    return true;
                }
    
                if(target < row[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
    
            return false;
        }
    };
    


    골랑 솔루션




    func searchMatrix(matrix [][]int, target int) bool {
        l, m, n := 0, len(matrix), len(matrix[0])
        r := m - 1
        var mid int
    
        for l <= r {
            mid = l + (r - l) / 2
    
            if target >= matrix[mid][0] && target <= matrix[mid][n - 1] {
                return binarySearch(matrix[mid], n, target)
            }
    
            if target < matrix[mid][0] {
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
    
        return false
    }
    
    func binarySearch(row []int, n, target int) bool {
        l, r := 0, n - 1
        var mid int
    
        for l <= r {
            mid = l + (r - l) / 2
    
            if target == row[mid] {
                return true
            }
    
            if target < row[mid] {
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
    
        return false
    }
    


    자바스크립트 솔루션




    var searchMatrix = function(matrix, target) {
        let l = 0, m = matrix.length, n = matrix[0].length;
        let r = m - 1;
        let mid;
    
        while(l <= r) {
            mid = Math.floor(l + (r - l) / 2);
    
            if(target >= matrix[mid][0] && target <= matrix[mid][n - 1]) {
                return binarySearch(matrix[mid], n, target);
            }
    
            if(target < matrix[mid][0]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
    
        return false;
    };
    
    var binarySearch = function(row, n, target) {
        let l = 0, r = n - 1;
        let mid;
    
        while(l <= r) {
            mid = Math.floor(l + (r - l) / 2);
    
            if(target == row[mid]) {
                return true;
            }
    
            if(target < row[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
    
        return false;
    };
    


    솔루션이 어떻게 작동하는지 알아보기 위해 알고리즘을 시험 실행해 보겠습니다.

    Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
           target = 3
    
    // searchMatrix function
    Step 1: l = 0
            m = matrix.size()
              = 3
            n = matrix[0].size()
              = 4
            r = m - 1
              = 2
    
    Step 2: loop while l <= r
              0 <= 2
              true
    
              mid = l + (r - l) / 2
                  = 0 + (2 - 0) / 2
                  = 1
    
              if target >= matrix[mid][0] && target <= matrix[mid][n - 1]
                 3 >= matrix[1][0] && 3 <= matrix[1][3]
                 3 >= 10 && 3 <= 20
                 false
    
              if target < matrix[mid][0]
                 3 < matrix[1][0]
                 3 < 10
                 true
    
                 r = mid - 1
                   = 1 - 1
                   = 0
    
    Step 3: loop while l <= r
              0 <= 0
              true
    
              mid = l + (r - l) / 2
                  = 0 + (0 - 0) / 2
                  = 0
    
              if target >= matrix[mid][0] && target <= matrix[mid][n - 1]
                 3 >= matrix[0][0] && 3 <= matrix[0][3]
                 3 >= 1 && 3 <= 7
                 true
    
                 return binarySearch(matrix[mid], n, target)
                        binarySearch(matrix[0], 4, 3)
    
    // binarySearch function
    Step 4: l = 0
            r = n - 1
              = 3
    
    Step 5: loop while l < r
              0 <= 3
    
              mid = l + (r - l) / 2
                  = 0 + (3 - 1) / 2
                  = 1
    
              if row[mid] == target
                 row[1] == 3
                 3 == 3
                 true
    
              We return to step 3
    
    Step 6: return binarySearch(matrix[mid], n, target)
    
    We return the answer as true.
    

    좋은 웹페이지 즐겨찾기