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.