Dată o matrice sortată împreună cu[][] de dimensiune n × m și un număr întreg x determinați dacă x este prezent în matrice.
Matricea este sortată în felul următor:
- Fiecare rând este sortat în ordine crescătoare.
- Primul element al fiecărui rând este mai mare sau egal cu ultimul element al rândului anterior
(adică mat[i][0] ≥ mat[i−1][m−1] pentru toți 1 ≤ i< n).
Exemple:
Intrare: x = 14 mat[][] = [[ 1 5 9]
[14 20 21]
[30 34 43]]
Ieșire: adevărat
Explicaţie: Valoarea14este prezent în al doilea rând prima coloană a matricei.Intrare: x = 42 mat[][] = [[ 1 5 9 11]
[14 20 21 26]
[30 34 43 50]]
Ieșire: fals
Explicaţie: Valoarea42nu apare în matrice.
Cuprins
- [Abordare naivă] Compararea cu toate elementele – O(n × m) Timp și O(1) Spațiu
- [Abordare mai bună] Utilizarea Căutării binare de două ori - O (log n + log m) Timp și O (1) spațiu
- [Abordare așteptată] Utilizarea căutării binare o dată - O(log(n × m)) și O(1) spațiu
[Abordare naivă] Compararea cu toate elementele – O(n × m) Timp și O(1) Spațiu
C++Ideea este să iterați întreaga matrice [][] și să comparați fiecare element cu x. Dacă un element se potrivește cu x, vom returna adevărat. În caz contrar, la sfârșitul traversării vom returna 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');
Ieșire
true
[Abordare mai bună] Utilizarea Căutării binare de două ori - O (log n + log m) Timp și O (1) spațiu
Mai întâi găsim rândul în care ar putea fi ținta x utilizând căutarea binară și apoi aplicăm din nou căutarea binară în acel rând. Pentru a găsi rândul corect, efectuăm căutare binară pe primele elemente ale rândului din mijloc.
Implementări pas cu pas:
=> Începe cu low = 0 și high = n - 1.
=> Dacă x este mai mic decât primul element al rândului din mijloc (a[mid][0]), atunci x va fi mai mic decât toate elementele din rânduri >= mid, așa că actualizați high = mid - 1.
=> Dacă x este mai mare decât primul element al rândului din mijloc (a[mid][0]), atunci x va fi mai mare decât toate elementele din rânduri< mid so store the current mid row and update low = mid + 1.
Odată ce am găsit rândul corect, putem aplica căutarea binară în acel rând pentru a căuta elementul țintă 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');
Ieșire
true
[Abordare așteptată] Utilizarea căutării binare o dată - O(log(n × m)) și O(1) spațiu
Ideea este de a considera matricea dată ca o matrice 1D și de a aplica o singură căutare binară.
De exemplu, pentru o matrice de dimensiune n x m și o putem considera ca o matrice 1D de dimensiune n*m, atunci primul indice ar fi 0 și ultimul indice n*m-1. Deci trebuie să facem căutare binară de la low = 0 la high = (n*m-1).
Cum să găsiți elementul în matricea 2D corespunzătoare indexului = mijloc?
C++Deoarece fiecare rând de mat[][] va avea m elemente, astfel încât să putem găsi rând a elementului ca (mijlocul / m) iar cel coloană a elementului ca (media % m) . Apoi putem compara x cu arr[mid/m][mid%m] pentru fiecare mijloc și completăm căutarea noastră binară.
#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');
Ieșire
trueCreați un test