정렬된 행렬이 주어지면 [][]와 함께 크기 n × m 및 정수 엑스 x가 행렬에 존재하는지 확인합니다.
행렬은 다음과 같은 방식으로 정렬됩니다.
- 각 행은 오름차순으로 정렬됩니다.
- 각 행의 첫 번째 요소는 이전 행의 마지막 요소보다 크거나 같습니다.
(즉, 모든 1 ≤ i에 대해 mat[i][0] ≥ mat[i−1][m−1]< n).
예:
입력: x = 14 매트[][] = [[ 1 5 9]
[14 20 21]
[30 34 43]]
산출: 진실
설명: 가치14행렬의 두 번째 행 첫 번째 열에 존재합니다.입력: x = 42 매트[][] = [[ 1 5 9 11]
[14 20 21 26]
[30 34 43 50]]
산출: 거짓
설명: 가치42매트릭스에는 나타나지 않습니다.
목차
- [순진한 접근 방식] 모든 요소 비교 – O(n × m) 시간 및 O(1) 공간
- [더 나은 접근 방식] 이진 검색을 두 번 사용 - O(log n + log m) 시간 및 O(1) 공간
- [예상 접근법] 이진 검색을 한 번만 사용 - O(log(n × m)) 및 O(1) 공간
[순진한 접근 방식] 모든 요소 비교 - O(n × m) 시간 및 O(1) 공간
C++아이디어는 전체 행렬 mat[][]를 반복하고 각 요소를 x와 비교하는 것입니다. 요소가 x와 일치하면 true를 반환합니다. 그렇지 않으면 순회가 끝나면 false를 반환합니다.
#include
class GfG { public static boolean searchMatrix(int[][] mat int x) { int n = mat.length; int m = mat[0].length; // traverse every element in the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == x) return true; } } return false; } public static void main(String[] args) { int[][] mat = { {1 5 9} {14 20 21} {30 34 43} }; int x = 14; System.out.println(searchMatrix(mat x) ? 'true' : 'false'); } }
def searchMatrix(mat x): n = len(mat) m = len(mat[0]) # traverse every element in the matrix for i in range(n): for j in range(m): if mat[i][j] == x: return True return False if __name__ == '__main__': mat = [ [1 5 9] [14 20 21] [30 34 43] ] x = 14 print('true' if searchMatrix(mat x) else 'false')
using System; class GfG { public static bool searchMatrix(int[][] mat int x) { int n = mat.Length; int m = mat[0].Length; // traverse every element in the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == x) return true; } } return false; } public static void Main(string[] args) { int[][] mat = new int[][] { new int[] {1 5 9} new int[] {14 20 21} new int[] {30 34 43} }; int x = 14; Console.WriteLine(searchMatrix(mat x) ? 'true' : 'false'); } }
function searchMatrix(mat x) { let n = mat.length; let m = mat[0].length; // traverse every element in the matrix for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (mat[i][j] === x) return true; } } return false; } // Driver Code let mat = [ [1 5 9] [14 20 21] [30 34 43] ]; let x = 14; console.log(searchMatrix(mat x) ? 'true' : 'false');
산출
true
[더 나은 접근 방식] 이진 검색을 두 번 사용 - O(log n + log m) 시간 및 O(1) 공간
먼저 이진 검색을 사용하여 대상 x가 있을 수 있는 행을 찾은 다음 해당 행 내에서 다시 이진 검색을 적용합니다. 올바른 행을 찾기 위해 중간 행의 첫 번째 요소에 대해 이진 검색을 수행합니다.
단계별 구현:
=> 낮은 = 0, 높은 = n - 1로 시작합니다.
=> x가 중간 행의 첫 번째 요소(a[mid][0])보다 작으면 x는 >= mid 행의 모든 요소보다 작으므로 high = mid - 1로 업데이트됩니다.
=> x가 중간 행의 첫 번째 요소(a[mid][0])보다 크면 x는 행의 모든 요소보다 큽니다.< mid so store the current mid row and update low = mid + 1.
올바른 행을 찾으면 해당 행 내에서 이진 검색을 적용하여 대상 요소 x를 검색할 수 있습니다.
C++#include
class GfG { // function to binary search for x in arr[] static boolean search(int[] arr int x) { int lo = 0 hi = arr.length - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (x == arr[mid]) return true; if (x < arr[mid]) hi = mid - 1; else lo = mid + 1; } return false; } // function to search element x in fully // sorted matrix static boolean searchMatrix(int[][] mat int x) { int n = mat.length m = mat[0].length; int lo = 0 hi = n - 1; int row = -1; while (lo <= hi) { int mid = (lo + hi) / 2; // if the first element of mid row is equal to x // return true if (x == mat[mid][0]) return true; // if x is greater than first element of mid row // store the mid row and search in lower half if (x > mat[mid][0]) { row = mid; lo = mid + 1; } // if x is smaller than first element of mid row // search in upper half else hi = mid - 1; } // if x is smaller than all elements of mat[][] if (row == -1) return false; return search(mat[row] x); } public static void main(String[] args) { int[][] mat = { {1 5 9} {14 20 21} {30 34 43} }; int x = 14; if (searchMatrix(mat x)) System.out.println('true'); else System.out.println('false'); } }
# function to binary search for x in arr[] def search(arr x): lo = 0 hi = len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if x == arr[mid]: return True if x < arr[mid]: hi = mid - 1 else: lo = mid + 1 return False # function to search element x in fully # sorted matrix def searchMatrix(mat x): n = len(mat) m = len(mat[0]) lo = 0 hi = n - 1 row = -1 while lo <= hi: mid = (lo + hi) // 2 # if the first element of mid row is equal to x # return true if x == mat[mid][0]: return True # if x is greater than first element of mid row # store the mid row and search in lower half if x > mat[mid][0]: row = mid lo = mid + 1 # if x is smaller than first element of mid row # search in upper half else: hi = mid - 1 # if x is smaller than all elements of mat[][] if row == -1: return False return search(mat[row] x) if __name__ == '__main__': mat = [[1 5 9] [14 20 21] [30 34 43]] x = 14 if searchMatrix(mat x): print('true') else: print('false')
using System; class GfG { // function to binary search for x in arr[] static bool Search(int[] arr int x) { int lo = 0 hi = arr.Length - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (x == arr[mid]) return true; if (x < arr[mid]) hi = mid - 1; else lo = mid + 1; } return false; } // function to search element x in fully // sorted matrix static bool SearchMatrix(int[][] mat int x) { int n = mat.Length m = mat[0].Length; int lo = 0 hi = n - 1; int row = -1; while (lo <= hi) { int mid = (lo + hi) / 2; // if the first element of mid row is equal to x // return true if (x == mat[mid][0]) return true; // if x is greater than first element of mid row // store the mid row and search in lower half if (x > mat[mid][0]) { row = mid; lo = mid + 1; } // if x is smaller than first element of mid row // search in upper half else hi = mid - 1; } // if x is smaller than all elements of mat[][] if (row == -1) return false; return Search(mat[row] x); } static void Main(string[] args) { int[][] mat = new int[][] { new int[] {1 5 9} new int[] {14 20 21} new int[] {30 34 43} }; int x = 14; if (SearchMatrix(mat x)) Console.WriteLine('true'); else Console.WriteLine('false'); } }
// function to binary search for x in arr[] function search(arr x) { let lo = 0 hi = arr.length - 1; while (lo <= hi) { let mid = Math.floor((lo + hi) / 2); if (x === arr[mid]) return true; if (x < arr[mid]) hi = mid - 1; else lo = mid + 1; } return false; } // function to search element x in fully // sorted matrix function searchMatrix(mat x) { let n = mat.length m = mat[0].length; let lo = 0 hi = n - 1; let row = -1; while (lo <= hi) { let mid = Math.floor((lo + hi) / 2); // if the first element of mid row is equal to x // return true if (x === mat[mid][0]) return true; // if x is greater than first element of mid row // store the mid row and search in lower half if (x > mat[mid][0]) { row = mid; lo = mid + 1; } // if x is smaller than first element of mid row // search in upper half else hi = mid - 1; } // if x is smaller than all elements of mat[][] if (row === -1) return false; return search(mat[row] x); } // Driver code const mat = [ [1 5 9] [14 20 21] [30 34 43] ]; const x = 14; if (searchMatrix(mat x)) console.log('true'); else console.log('false');
산출
true
[예상 접근법] 이진 검색을 한 번만 사용 - O(log(n × m)) 및 O(1) 공간
아이디어는 주어진 행렬을 1D 배열로 간주하고 하나의 이진 검색만 적용하는 것입니다.
예를 들어 n x m 크기의 행렬의 경우 이를 n*m 크기의 1D 배열로 간주하면 첫 번째 인덱스는 0이 되고 마지막 인덱스는 n*m-1이 됩니다. 따라서 low = 0부터 high = (n*m-1)까지 이진 검색을 수행해야 합니다.
index = mid에 해당하는 2D 행렬의 요소를 찾는 방법은 무엇입니까?
C++mat[][]의 각 행에는 m개의 요소가 있으므로 다음을 찾을 수 있습니다. 열 요소의 (중/m) 그리고 열 요소의 (중간%m) . 그런 다음 x를 각 mid에 대해 arr[mid/m][mid%m]과 비교하고 이진 검색을 완료할 수 있습니다.
#include
class GfG { static boolean searchMatrix(int[][] mat int x) { int n = mat.length m = mat[0].length; int lo = 0 hi = n * m - 1; while (lo <= hi) { int mid = (lo + hi) / 2; // find row and column of element at mid index int row = mid / m; int col = mid % m; // if x is found return true if (mat[row][col] == x) return true; // if x is greater than mat[row][col] search // in right half if (mat[row][col] < x) lo = mid + 1; // if x is less than mat[row][col] search // in left half else hi = mid - 1; } return false; } public static void main(String[] args) { int[][] mat = {{1 5 9} {14 20 21} {30 34 43}}; int x = 14; if (searchMatrix(mat x)) System.out.println('true'); else System.out.println('false'); } }
def searchMatrix(mat x): n = len(mat) m = len(mat[0]) lo hi = 0 n * m - 1 while lo <= hi: mid = (lo + hi) // 2 # find row and column of element at mid index row = mid // m col = mid % m # if x is found return true if mat[row][col] == x: return True # if x is greater than mat[row][col] search # in right half if mat[row][col] < x: lo = mid + 1 # if x is less than mat[row][col] search # in left half else: hi = mid - 1 return False if __name__ == '__main__': mat = [[1 5 9] [14 20 21] [30 34 43]] x = 14 if searchMatrix(mat x): print('true') else: print('false')
using System; class GfG { // function to search for x in the matrix // using binary search static bool searchMatrix(int[] mat int x) { int n = mat.GetLength(0) m = mat.GetLength(1); int lo = 0 hi = n * m - 1; while (lo <= hi) { int mid = (lo + hi) / 2; // find row and column of element at mid index int row = mid / m; int col = mid % m; // if x is found return true if (mat[row col] == x) return true; // if x is greater than mat[row col] search // in right half if (mat[row col] < x) lo = mid + 1; // if x is less than mat[row col] search // in left half else hi = mid - 1; } return false; } static void Main() { int[] mat = { { 1 5 9 } { 14 20 21 } { 30 34 43 } }; int x = 14; if (searchMatrix(mat x)) Console.WriteLine('true'); else Console.WriteLine('false'); } }
function searchMatrix(mat x) { let n = mat.length m = mat[0].length; let lo = 0 hi = n * m - 1; while (lo <= hi) { let mid = Math.floor((lo + hi) / 2); // find row and column of element at mid index let row = Math.floor(mid / m); let col = mid % m; // if x is found return true if (mat[row][col] === x) return true; // if x is greater than mat[row][col] search // in right half if (mat[row][col] < x) lo = mid + 1; // if x is less than mat[row][col] search // in left half else hi = mid - 1; } return false; } // Driver Code let mat = [[1 5 9] [14 20 21] [30 34 43]]; let x = 14; if (searchMatrix(mat x)) console.log('true'); else console.log('false');
산출
true퀴즈 만들기