Meklēšanas elements sakārtotā matricā
Dota sakārtota matrica kopā ar [][] ar lielumu n × m un veselu skaitli x noteikt, vai matricā ir x.
Matrica tiek sakārtota šādi:
- Katra rinda tiek sakārtota augošā secībā.
- Katras rindas pirmais elements ir lielāks vai vienāds ar iepriekšējās rindas pēdējo elementu
(t.i., mat[i][0] ≥ mat[i−1][m−1] visiem 1 ≤ i < n).
Piemēri:
Ievade: x = 14 mat[][] = [[1 5 9]
[14 20 21]
[30 34 43]]
Izvade: taisnība
Paskaidrojums: Vērtība14atrodas matricas otrās rindas pirmajā kolonnā.Ievade: x = 42 mat[][] = [[ 1 5 9 11]
[14 20 21 26]
[30 34 43 50]]
Izvade: viltus
Paskaidrojums: Vērtība42matricā neparādās.
Satura rādītājs
- [Naīvā pieeja] Salīdzinājums ar visiem elementiem – O(n × m) laiks un O(1) telpa
- [Labāka pieeja] Izmantojot bināro meklēšanu divreiz — O(log n + log m) laiks un O(1) telpa
- [Paredzamā pieeja] Izmantojot bināro meklēšanu vienreiz — O(log(n × m)) un O(1) atstarpe
[Naīvā pieeja] Salīdzinājums ar visiem elementiem – O(n × m) laiks un O(1) telpa
C++Ideja ir atkārtot visu matricas paklāju[][] un salīdzināt katru elementu ar x. Ja elements atbilst x, mēs atgriezīsim patiesu. Pretējā gadījumā šķērsošanas beigās mēs atgriezīsim false.
#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' );
Izvade
true
[Labāka pieeja] Izmantojot bināro meklēšanu divreiz — O(log n + log m) laiks un O(1) telpa
Vispirms mēs atrodam rindu, kurā varētu būt mērķis x, izmantojot bināro meklēšanu, un pēc tam šajā rindā atkal lietojam bināro meklēšanu. Lai atrastu pareizo rindu, veicam bināro meklēšanu vidējās rindas pirmajos elementos.
Soli pa solim ieviešanas:
=> Sāciet ar zemu = 0 un augstu = n - 1.
=> Ja x ir mazāks par vidējās rindas pirmo elementu (a[mid][0]), tad x būs mazāks par visiem elementiem rindās >= mid, tāpēc atjaunināšana high = mid - 1.
=> Ja x ir lielāks par vidējās rindas pirmo elementu (a[mid][0]), tad x būs lielāks par visiem rindu elementiem < mid so store the current mid row and update low = mid + 1.
Kad esam atraduši pareizo rindu, mēs varam izmantot bināro meklēšanu šajā rindā, lai meklētu mērķa elementu 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' );
Izvade
true
[Paredzamā pieeja] Izmantojot bināro meklēšanu vienreiz — O(log(n × m)) un O(1) atstarpe
Ideja ir uzskatīt doto matricu par 1D masīvu un izmantot tikai vienu bināro meklēšanu.
Piemēram, matricai ar izmēru n x m un mēs to varam uzskatīt par 1D masīvu ar izmēru n*m, tad pirmais indekss būtu 0 un pēdējais indekss būtu n*m-1. Tāpēc mums ir jāveic binārā meklēšana no zema = 0 līdz augstam = (n * m-1).
Kā 2D matricā atrast elementu, kas atbilst indeksam = mid?
C++Tā kā katrā paklāja rindā [][] būs m elementi, tāpēc mēs varam atrast rinda no elementa kā (vidus/m) un kolonnu no elementa kā (vidus % m) . Pēc tam mēs varam salīdzināt x ar arr[mid/m][mid%m] katram vidum un pabeigt bināro meklēšanu.
#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' );
Izvade
trueIzveidojiet viktorīnu
