在给定的矩阵中找到一个元素，使每一行和每一列都被排序。 例如：
null
Input : arr[] = { { 1, 2, 3}, { 4, 5, 6}, { 7, 8, 9} } element=5Output : Element Found at position (1, 1).Input : arr[]={ { 11, 21, 31, 41, 51 }, { 12, 22, 32, 42, 52 }, { 13, 23, 33, 43, 53 }, { 14, 24, 34, 44, 54 }, { 15, 25, 35, 45, 55 } } element=11Output : Element Found at position (0, 0).
A. 简单解决方案 就是一个接一个地搜索。该解的时间复杂度为O（n） 2. ). A. 更好的解决方案 就是 使用“分而治之”找到元素 .此解决方案的时间复杂度为O（n 1.58 ).请参考 这 详情请参阅本文。 下面是一个例子 有效解决方案 这在O（m+n）时间内有效。 1） 从左下角的元素开始 2） 循环：将这个元素e与x进行比较 ….i） 如果它们相等，则返回其位置 …ii）e x然后向右移动（如果超出矩阵的界限，则断开返回false） 3） 重复i）、ii）和iii）直到找到元素或返回false 感谢Devendraiit提出以下方法。 实施：
C++
// C++ program to search an element in row-wise // and column-wise sorted matrix #include<bits/stdc++.h> using namespace std; #define MAX 100 /* Searches the element x in mat[m][n]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ bool search( int mat[][MAX], int m, int n, int x) { int i = m-1, j = 0; //set indexes for bottom left element while ( i >= 0 && j < n ) { if ( mat[i][j] == x ) return true ; if ( mat[i][j] > x ) i--; else // if mat[i][j] < x j++; } return false ; } // driver program to test above function int main() { int mat[][MAX] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}, {50, 60, 70, 80}, }; if (search(mat, 5, 4, 29)) cout << "Yes" ; else cout << "No" ; return 0; } |
JAVA
// Java program to search an // element in row-wise and // column-wise sorted matrix class GFG { static final int MAX = 100 ; /* Searches the element x in mat[m][n]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ static boolean search( int mat[][], int m, int n, int x) { // set indexes for // bottom left element int i = m - 1 , j = 0 ; while (i >= 0 && j < n) { if (mat[i][j] == x) return true ; if (mat[i][j] > x) i--; else // if mat[i][j] < x j++; } return false ; } // Driver Code public static void main(String args[]) { int mat[][] = {{ 10 , 20 , 30 , 40 }, { 15 , 25 , 35 , 45 }, { 27 , 29 , 37 , 48 }, { 32 , 33 , 39 , 50 }, { 50 , 60 , 70 , 80 }}; if (search(mat, 5 , 4 , 29 )) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed // by Kirti_Mangal |
Python3
# Python program to search an element in # row-wise and column-wise sorted matrix # define MAX 100 # Searches the element x in mat[m][n]. # If the element is found, then prints # its position and returns true, otherwise # prints "not found" and returns false def search(mat, m, n, x): i, j = m - 1 , 0 # set indexes for bottom # left element while (i > = 0 and j < n): if (mat[i][j] = = x): return True ; if (mat[i][j] > x): i - = 1 else : # if mat[i][j] < x j + = 1 return False # Driver Code if __name__ = = '__main__' : mat = [[ 10 , 20 , 30 , 40 ], [ 15 , 25 , 35 , 45 ], [ 27 , 29 , 37 , 48 ], [ 32 , 33 , 39 , 50 ], [ 50 , 60 , 70 , 80 ]] if (search(mat, 5 , 4 , 29 )): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Rajput-Ji |
C#
// C# program to search an // element in row-wise and // column-wise sorted matrix using System; class GFG { /* Searches the element x in mat[m][n]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ static bool search( int [,] mat, int m, int n, int x) { // set indexes for // bottom left element int i = m - 1, j = 0; while (i >= 0 && j < n) { if (mat[i, j] == x) return true ; if (mat[i, j] > x) i--; else // if mat[i][j] < x j++; } return false ; } // Driver Code public static void Main() { int [,]mat = {{10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}, {50, 60, 70, 80}}; if (search(mat, 5, 4, 29)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php // PHP program to search an element in row-wise // and column-wise sorted matrix $MAX = 100; /* Searches the element x in mat[m][n]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ function search( $mat , $m , $n , $x ) { $i = $m - 1; $j = 0; // set indexes for bottom left element while ( $i >= 0 && $j < $n ) { if ( $mat [ $i ][ $j ] == $x ) return true; if ( $mat [ $i ][ $j ] > $x ) $i --; else // if mat[i][j] < x $j ++; } return false; } // Driver Code $mat = array ( array (10, 20, 30, 40), array (15, 25, 35, 45), array (27, 29, 37, 48), array (32, 33, 39, 50), array (50, 60, 70, 80)); if (search( $mat , 5, 4, 29)) echo "Yes" ; else echo "No" ; // This code is contributed by mits ?> |
Javascript
<script> // JavaScript program to search an // element in row-wise and // column-wise sorted matrix /* Searches the element x in mat[m][n]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ function search(mat, m, n, x) { // set indexes for // bottom left element var i = m - 1, j = 0; while (i >= 0 && j < n) { if (mat[i][j] == x) return true ; if (mat[i][j] > x) i--; else // if mat[i][j] < x j++; } return false ; } // Driver Code var mat = [[10, 20, 30, 40], [15, 25, 35, 45], [27, 29, 37, 48], [32, 33, 39, 50], [50, 60, 70, 80]]; if (search(mat, 5, 4, 29)) document.write( "Yes" ); else document.write( "No" ); </script> |
输出：
Yes
时间复杂性： O（m+n） 也可以从右上角开始执行上述操作。请看 在按行和按列排序的矩阵中搜索 用于替代实现。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
