74. Search a 2D Matrix
문제 설명
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.
행렬에서 target 이 있는지 판별하는 문제이다.
Example
> 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
Idea
우선 이 문제의 조건은 각 행의 숫자가 오름차순으로 정렬되어있고 각 행의 마지막 숫자는 다음 행의 첫 숫자보다 낮게 정렬되있다. 그래서 target값을 찾는데 이진탐색을 이용했고
n차원 배열로 되어있는 matrix값을 flat 메소드를 이용해 1차원 배열로 변환하여 쉽게 값을 찾아냄
Solution
var searchMatrix = function(matrix, target) { matrix = matrix.flat() let left = 0 let right = matrix.length-1 while(left<=right){ const mid = Math.floor((left+right) / 2) if(matrix[mid] === target) return true matrix[mid] > target ? right= mid-1 : left = mid+1 } return false };
Author And Source
이 문제에 관하여(74. Search a 2D Matrix), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsh__97/74.-Search-a-2D-Matrix저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)