ソートされた行列が与えられた場合 とともに[][] サイズ 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は行列の 2 行目の 1 列目に存在します。入力： x = 42 マット[][] = [[ 1 5 9 11]
[14 20 21 26]
[30 34 43 50]]
出力： 間違い
説明： 値42マトリックスには登場しません。
目次
- [素朴なアプローチ] すべての要素で比較 – O(n × m) 時間と O(1) 空間
- [より良いアプローチ] 二分探索を 2 回使用する - O(log n + log m) 時間と O(1) 空間
- [想定されるアプローチ] 二分探索を 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
[より良いアプローチ] 二分探索を 2 回使用する - 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
[想定されるアプローチ] 二分探索を 1 回使用 - O(log(n × m)) および O(1) 空間
このアイデアは、指定された行列を 1D 配列と見なし、二分探索を 1 回だけ適用することです。
たとえば、サイズが n x m の行列の場合、それをサイズ n*m の 1D 配列とみなすことができ、最初のインデックスは 0 になり、最後のインデックスは n*m-1 になります。したがって、low = 0 から high = (n*m-1) まで二分探索を行う必要があります。
2D行列でindex = Midに対応する要素を見つけるにはどうすればよいですか?
C++mat[][] の各行には m 個の要素があるため、 行 要素の (ミッド/メートル) そして カラム 要素の (中間%m) 。次に、各 Mid について x を 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クイズの作成