LeetCode - 2D 매트릭스 검색
23923 단어 programmingjavascriptgoalgorithms
문제 설명
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.
Reference
이 문제에 관하여(LeetCode - 2D 매트릭스 검색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/_alkesh26/leetcode-search-a-2d-matrix-2m1m텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)