logo

TechCodeview

Keresés elem egy rendezett mátrixban

Adott egy rendezett mátrix együtt [][] n × m méretű és egész szám x határozza meg, hogy x szerepel-e a mátrixban.
A mátrix rendezése a következőképpen történik:

  • Az egyes sorok növekvő sorrendben vannak rendezve.
  • Minden sor első eleme nagyobb vagy egyenlő, mint az előző sor utolsó eleme
    (azaz mat[i][0] ≥ mat[i−1][m−1] minden 1 ≤ i< n).

Példák:

Bemenet: x = 14 mat[][] = [[ 1 5 9]
[14 20 21]
[30 34 43]]
Kimenet: igaz
Magyarázat: Az érték14a mátrix második sorának első oszlopában van jelen.



Bemenet: x = 42 mat[][] = [[ 1 5 9 11]
[14 20 21 26]
[30 34 43 50]]
Kimenet: hamis
Magyarázat: Az érték42nem jelenik meg a mátrixban.

Tartalomjegyzék

[Naiv megközelítés] Összehasonlítás minden elemmel – O(n × m) idő és O(1) tér

Az ötlet az, hogy a teljes mátrixmat[][] iteráljuk, és minden elemet összehasonlítunk x-szel. Ha egy elem egyezik az x-szel, akkor igazat adunk vissza. Ellenkező esetben a bejárás végén false-t adunk vissza.

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');

Kimenet 
true

[Jobb megközelítés] Bináris keresés kétszeri használata – O(log n + log m) idő és O(1) tér

Először bináris kereséssel keressük meg azt a sort, ahol a cél x lehet, majd ismét alkalmazzuk a bináris keresést a sorban. A megfelelő sor megtalálásához bináris keresést végzünk a középső sor első elemeire.

Lépésről lépésre való megvalósítás:

=> Kezdje alacsony = 0 és magas = n - 1 értékkel.
=> Ha x kisebb, mint a középső sor első eleme (a[mid][0]), akkor x kisebb lesz, mint a >= mid sorok összes eleme, tehát frissítés high = mid - 1.
=> Ha x nagyobb, mint a középső sor első eleme (a[mid][0]), akkor x nagyobb lesz, mint a sorok összes eleme< mid so store the current mid row and update low = mid + 1.

Ha megtaláltuk a megfelelő sort, alkalmazhatunk bináris keresést abban a sorban, hogy megkeressük az x célelemet.

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');

Kimenet 
true

[Elvárt megközelítés] Bináris keresés egyszeri használatával - O(log(n × m)) és O(1) szóköz

Az ötlet az, hogy az adott mátrixot 1D tömbnek tekintjük, és csak egy bináris keresést alkalmazunk.
Például egy n x m méretű mátrix esetén, és tekinthetjük n*m méretű 1D tömbnek, akkor az első index 0, az utolsó index pedig n*m-1. Tehát bináris keresést kell végeznünk az alacsony = 0-tól a magas = (n*m-1) értékig.

Hogyan találjuk meg a 2D mátrixban az index = midnek megfelelő elemet?

Mivel a mat[][] minden sorában m elem lesz, így megtalálhatjuk a sor az elemről mint (közepe / m) és a oszlop az elemről mint (közepe % m) . Ezután összehasonlíthatjuk x-et az arr[mid/m][mid%m] értékkel minden mid esetén, és befejezhetjük a bináris keresést.

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');

Kimenet 
true
Kvíz létrehozása