logo

TechCodeview

Hae elementtiä järjestetyssä matriisissa

Annettu lajiteltu matriisi yhdessä [][] jonka koko on n × m ja kokonaisluku x määrittää, onko x matriisissa.
Matriisi lajitellaan seuraavasti:

  • Jokainen rivi on lajiteltu kasvavaan järjestykseen.
  • Kunkin rivin ensimmäinen elementti on suurempi tai yhtä suuri kuin edellisen rivin viimeinen elementti
    (eli mat[i][0] ≥ mat[i−1][m−1] kaikille 1 ≤ i< n).

Esimerkkejä:

Syöte: x = 14 matto[][] = [[ 1 5 9]
[14 20 21]
[30 34 43]]
Lähtö: totta
Selitys: Arvo14on matriisin toisen rivin ensimmäisessä sarakkeessa.



Syöte: x = 42 matto[][] = [[ 1 5 9 11]
[14 20 21 26]
[30 34 43 50]]
Lähtö: väärä
Selitys: Arvo42ei näy matriisissa.

Sisällysluettelo

[Naiivi lähestymistapa] Vertaamalla kaikkiin elementteihin – O(n × m) aika ja O(1) avaruus

Ajatuksena on iteroida koko matriisimatto[][] ja verrata jokaista elementtiä x:ään. Jos elementti vastaa x:ää, palautetaan tosi. Muussa tapauksessa palautamme läpikulun lopussa false.

C++ 
#include    #include  using namespace std; bool searchMatrix(vector<vector<int>>& mat int x) {  int n = mat.size();  int m = mat[0].size();  // 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; } int main() {  vector<vector<int>> mat = {  {1 5 9}  {14 20 21}  {30 34 43}  };  int x = 14;  cout << (searchMatrix(mat x) ? 'true' : 'false') << endl; }
Java 
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');  } }
Python 
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')
C# 
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');  } }
JavaScript 
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');

Lähtö 
true

[Parempi lähestymistapa] Binäärihaun käyttäminen kahdesti - O(log n + log m) aika ja O(1)-avaruus

Ensin paikannamme binäärihaun avulla rivin, jossa kohde x saattaa olla, ja käytämme sitten binäärihakua uudelleen kyseisellä rivillä. Oikean rivin löytämiseksi suoritamme binäärihaun keskirivin ensimmäisille elementeille.

Vaiheittaiset toteutukset:

=> Aloita matalasta = 0 ja korkeasta = n - 1.
=> Jos x on pienempi kuin keskirivin ensimmäinen elementti (a[mid][0]), niin x on pienempi kuin kaikki rivin elementit >= mid, joten päivitä high = mid - 1.
=> Jos x on suurempi kuin keskirivin ensimmäinen elementti (a[mid][0]), x on suurempi kuin kaikki rivien elementit< mid so store the current mid row and update low = mid + 1.

Kun olemme löytäneet oikean rivin, voimme käyttää binäärihakua kyseisellä rivillä etsimään kohdeelementtiä x.

C++ 
#include    #include  using namespace std; // function to binary search for x in arr[] bool search(vector<int> &arr int x) {  int lo = 0 hi = arr.size() - 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 bool searchMatrix(vector<vector<int>> &mat int x) {  int n = mat.size() m = mat[0].size();  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); } int main() {  vector<vector<int>> mat = {{1 5 9} {14 20 21} {30 34 43}};  int x = 14;  if (searchMatrix(mat x))  cout << 'true';  else  cout << 'false';  return 0; }
Java 
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');  } }
Python 
# 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')
C# 
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');  } }
JavaScript 
// 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');

Lähtö 
true

[Odotettu lähestymistapa] Kerran binäärihaun käyttäminen - O(log(n × m)) ja O(1)-välilyönti

Ajatuksena on pitää annettua matriisia 1D-taulukona ja käyttää vain yhtä binaarihakua.
Esimerkiksi matriisille, jonka koko on n x m ja voimme pitää sitä 1D-taulukona, jonka koko on n*m, niin ensimmäinen indeksi olisi 0 ja viimeinen indeksi n*m-1. Joten meidän on tehtävä binäärihaku arvosta alhainen = 0 arvoon korkea = (n*m-1).

Kuinka löytää 2D-matriisista elementti, joka vastaa indeksi = mid?

Koska jokaisella maton [][] rivillä on m elementtiä, voimme löytää rivi elementistä kuin (keski/m) ja sarakkeessa elementistä kuin (kesk. % m) . Sitten voimme verrata x:ää arvoon arr[mid/m][mid%m] jokaiselle midille ja suorittaa binäärihakumme.

C++ 
#include    #include  using namespace std; bool searchMatrix(vector<vector<int>>& mat int x) {  int n = mat.size() m = mat[0].size();  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; } int main() {  vector<vector<int>> mat = {{1 5 9}   {14 20 21}   {30 34 43}};  int x = 14;  if (searchMatrix(mat x))  cout << 'true';  else  cout << 'false';  return 0; }
Java 
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');  } }
Python 
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')
C# 
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');  } }
JavaScript 
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');

Lähtö 
true
Luo tietokilpailu