문제 URL : https://leetcode.com/problems/search-a-2d-matrix/
Search a 2D Matrix - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제 접근법 :
매우 쉬운 문제입니다. O^2탐색을 했다면 안보셔도 됩니다. 하지만 문제 형식이
binary search를 사용해서 풀라고 하듯이 배열값에 조건을 줬으니 binary search를 써서 풀어보자구여
배열의 사이즈를 n,m이라할때
모든행의 가장 왼쪽과 오른쪽에 target이 존재 가능성이 있는지 확인합니다.
그럼 그 하나의 행만 조사해서 이진탐색을 이용하면되겠죠? 아니면 필요없을테니
그럼 있다면 lower_bound를 사용해서 해당 값이 target과 일치하는지 확인해주면 됩니다.
따라서 이렇게하면 시간복잡도는 O(n) + O(Log2n) - >O(n)이라 할수있습니다.
O(N^2)은 너무쉬우니 O(n)까지 줄여보자구여
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = 0, m = matrix[0].size();
int left = 0, right = m - 1;
int idx = -1;
for (int i = 0; i < matrix.size(); i++) {
if (matrix[i][left] <= target && target <= matrix[i][right])
idx = i;
}
if (idx == -1)return false;
int t = lower_bound(matrix[idx].begin(), matrix[idx].end(), target)-matrix[idx].begin();
if (t >= m)return false;
return matrix[idx][t] == target;
}
};
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.
'LeetCode' 카테고리의 다른 글
| LeetCode Valid Sudoku (1) | 2023.06.16 |
|---|---|
| LeetCode (0) | 2022.11.11 |
| LeetCode 112 Path Sum (0) | 2021.11.14 |
| LeetCode 257 Binary Tree Paths (0) | 2021.11.14 |
| LeetCode 103. Binary Tree Zigzag Level Order Traversal (0) | 2021.08.03 |
