给定一个nxn矩阵和一个数x，求x在矩阵中的位置（如果存在）。否则，请打印“未找到”。在给定的矩阵中，每一行和每一列都按递增顺序排序。所设计的算法应具有线性时间复杂度。
null
例子：
Input: mat[4][4] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}}; x = 29Output: Found at (2, 1)Explanation: Element at (2,1) is 29Input : mat[4][4] = { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}}; x = 100Output : Element not foundExplanation: Element 100 is not found
简单解决方案
- 方法： 简单的方法是遍历数组并逐个搜索元素。
- 算法：
- 运行嵌套循环，外部循环用于行，内部循环用于列
- 用x检查每个元素，如果找到元素，则打印“元素已找到”
- 如果未找到元素，则打印“未找到元素”。
- 实施：
CPP14
// C++ program to search an element in row-wise // and column-wise sorted matrix #include <bits/stdc++.h> using namespace std; /* Searches the element x in mat[][]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ int search( int mat[4][4], int n, int x) { if (n == 0) return -1; //traverse through the matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) //if the element is found if (mat[i][j] == x) { cout<< "Element found at (" << i << ", " << j << ")" ; return 1; } } cout << "n Element not found" ; return 0; } // Driver code int main() { int mat[4][4] = { { 10, 20, 30, 40 }, { 15, 25, 35, 45 }, { 27, 29, 37, 48 }, { 32, 33, 39, 50 } }; search(mat, 4, 29); return 0; } |
JAVA
// Java program to search an element in row-wise // and column-wise sorted matrix class GFG { static int search( int [][] mat, int n, int x) { if (n == 0 ) return - 1 ; // traverse through the matrix for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) // if the element is found if (mat[i][j] == x) { System.out.print( "Element found at (" + i + ", " + j + ")" ); return 1 ; } } System.out.print( " Element not found" ); return 0 ; } public static void main(String[] args) { int mat[][] = { { 10 , 20 , 30 , 40 }, { 15 , 25 , 35 , 45 }, { 27 , 29 , 37 , 48 }, { 32 , 33 , 39 , 50 } }; search(mat, 4 , 29 ); } } |
Python3
# Python program to search an element in row-wise # and column-wise sorted matrix # Searches the element x in mat[][]. If the # element is found, then prints its position # and returns true, otherwise prints "not found" # and returns false def search(mat, n, x): if (n = = 0 ): return - 1 # Traverse through the matrix for i in range (n): for j in range (n): # If the element is found if (mat[i][j] = = x): print ( "Element found at (" , i, "," , j, ")" ) return 1 print ( " Element not found" ) return 0 # Driver code mat = [[ 10 , 20 , 30 , 40 ], [ 15 , 25 , 35 , 45 ],[ 27 , 29 , 37 , 48 ],[ 32 , 33 , 39 , 50 ]] search(mat, 4 , 29 ) # This code is contributed by rag2127 |
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[][]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ static int search( int [,] mat, int n, int x) { if (n == 0) return -1; // Traverse through the matrix for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) // If the element is found if (mat[i,j] == x) { Console.Write( "Element found at (" + i + ", " + j + ")" ); return 1; } } Console.Write( " Element not found" ); return 0; } // Driver code static public void Main() { int [,] mat = { { 10, 20, 30, 40 }, { 15, 25, 35, 45 }, { 27, 29, 37, 48 }, { 32, 33, 39, 50 } }; search(mat, 4, 29); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Java Script program to search an element in row-wise // and column-wise sorted matrix function search(mat,n,x) { if (n == 0) return -1; // traverse through the matrix for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) // if the element is found if (mat[i][j] == x) { document.write( "Element found at (" + i + ", " + j + ")<br>" ); return 1; } } document.write( " Element not found" ); return 0; } let mat = [[ 10, 20, 30, 40 ], [15, 25, 35, 45] , [ 27, 29, 37, 48 ], [ 32, 33, 39, 50 ]]; search(mat, 4, 29); //contributed by 171fa07058 </script> |
输出
Element found at (2, 1)
更好的解决方案是 使用“分而治之”找到元素 它具有时间复杂性 O（n）的 1.58 ).请参考 在这里 详细信息。
有效解决方案
- 方法： 简单的方法是在每次比较中删除一行或一列，直到找到一个元素。从矩阵的右上角开始搜索。有三种可能的情况。
- 给定数字大于当前数字： 这将确保当前行中的所有元素都小于给定的数字，因为指针已经位于最右边的元素，并且该行已排序。因此，整行将被删除，并继续搜索下一行。在这里，消去意味着不需要搜索一行。
- 给定的数字小于当前数字： 这将确保当前列中的所有元素都大于给定的数字。因此，整个列将被删除，并继续搜索前一列，即最左边的列。
- 给定的数字等于当前的数字： 这将结束搜索。
- 算法：
- 设给定元素为x，创建两个变量 i=0，j=n-1 作为行和列的索引
- 运行一个循环，直到i=n
- 检查当前元素是否大于x，然后减少j的计数。排除当前列。
- 检查当前元素是否小于x，然后增加i的计数。排除当前行。
- 如果元素相等，则打印位置和结束。
- 感谢Devendraiit提出以下方法。
- 实施：
C++
// C++ program to search an element in row-wise // and column-wise sorted matrix #include <bits/stdc++.h> using namespace std; /* Searches the element x in mat[][]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ int search( int mat[4][4], int n, int x) { if (n == 0) return -1; int smallest = mat[0][0], largest = mat[n - 1][n - 1]; if (x < smallest || x > largest) return -1; // set indexes for top right element int i = 0, j = n - 1; while (i < n && j >= 0) { if (mat[i][j] == x) { cout << "n Found at " << i << ", " << j; return 1; } if (mat[i][j] > x) j--; // Check if mat[i][j] < x else i++; } cout << "n Element not found" ; return 0; } // Driver code int main() { int mat[4][4] = { { 10, 20, 30, 40 }, { 15, 25, 35, 45 }, { 27, 29, 37, 48 }, { 32, 33, 39, 50 } }; search(mat, 4, 29); return 0; } // This code is contributed // by Akanksha Rai(Abby_akku) |
C
// C program to search an element in row-wise // and column-wise sorted matrix #include <stdio.h> /* Searches the element x in mat[][]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ int search( int mat[4][4], int n, int x) { if (n == 0) return -1; int smallest = mat[0][0], largest = mat[n - 1][n - 1]; if (x < smallest || x > largest) return -1; // set indexes for top right element int i = 0, j = n - 1; while (i < n && j >= 0) { if (mat[i][j] == x) { printf ( " Found at %d, %d" , i, j); return 1; } if (mat[i][j] > x) j--; else // if mat[i][j] < x i++; } printf ( "n Element not found" ); return 0; // if ( i==n || j== -1 ) } // driver program to test above function int main() { int mat[4][4] = { { 10, 20, 30, 40 }, { 15, 25, 35, 45 }, { 27, 29, 37, 48 }, { 32, 33, 39, 50 }, }; search(mat, 4, 29); return 0; } |
JAVA
// JAVA Code for Search in a row wise and // column wise sorted matrix class GFG { /* Searches the element x in mat[][]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ private static void search( int [][] mat, int n, int x) { // set indexes for top right int i = 0 , j = n - 1 ; // element while (i < n && j >= 0 ) { if (mat[i][j] == x) { System.out.print( "n Found at " + i + " " + j); return ; } if (mat[i][j] > x) j--; else // if mat[i][j] < x i++; } System.out.print( "n Element not found" ); return ; // if ( i==n || j== -1 ) } // driver program to test above function public static void main(String[] args) { int mat[][] = { { 10 , 20 , 30 , 40 }, { 15 , 25 , 35 , 45 }, { 27 , 29 , 37 , 48 }, { 32 , 33 , 39 , 50 } }; search(mat, 4 , 29 ); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# Python3 program to search an element # in row-wise and column-wise sorted matrix # Searches the element x in mat[][]. If the # element is found, then prints its position # and returns true, otherwise prints "not found" # and returns false def search(mat, n, x): i = 0 # set indexes for top right element j = n - 1 while ( i < n and j > = 0 ): if (mat[i][j] = = x ): print ( "n Found at " , i, ", " , j) return 1 if (mat[i][j] > x ): j - = 1 # if mat[i][j] < x else : i + = 1 print ( "Element not found" ) return 0 # if (i == n || j == -1 ) # Driver Code mat = [ [ 10 , 20 , 30 , 40 ], [ 15 , 25 , 35 , 45 ], [ 27 , 29 , 37 , 48 ], [ 32 , 33 , 39 , 50 ] ] search(mat, 4 , 29 ) # This code is contributed by Anant Agarwal. |
C#
// C# Code for Search in a row wise and // column wise sorted matrix using System; class GFG { /* Searches the element x in mat[][]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ private static void search( int [, ] mat, int n, int x) { // set indexes for top right // element int i = 0, j = n - 1; while (i < n && j >= 0) { if (mat[i, j] == x) { Console.Write( "n Found at " + i + ", " + j); return ; } if (mat[i, j] > x) j--; else // if mat[i][j] < x i++; } Console.Write( "n Element not found" ); return ; // if ( i==n || j== -1 ) } // driver program to test above function public static void Main() { int [, ] mat = { { 10, 20, 30, 40 }, { 15, 25, 35, 45 }, { 27, 29, 37, 48 }, { 32, 33, 39, 50 } }; search(mat, 4, 29); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to search an // element in row-wise and // column-wise sorted matrix /* Searches the element $x in mat[][]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ function search(& $mat , $n , $x ) { $i = 0; $j = $n - 1; // set indexes for // top right element while ( $i < $n && $j >= 0) { if ( $mat [ $i ][ $j ] == $x ) { echo "n found at " . $i . ", " . $j ; return 1; } if ( $mat [ $i ][ $j ] > $x ) $j --; else // if $mat[$i][$j] < $x $i ++; } echo "n Element not found" ; return 0; // if ( $i==$n || $j== -1 ) } // Driver Code $mat = array ( array (10, 20, 30, 40), array (15, 25, 35, 45), array (27, 29, 37, 48), array (32, 33, 39, 50)); search( $mat , 4, 29); // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // JAVA SCRIPT Code for Search in a row wise and // column wise sorted matrix /* Searches the element x in mat[][]. If the element is found, then prints its position and returns true, otherwise prints "not found" and returns false */ function search(mat,n,x){ // set indexes for top right let i = 0, j = n - 1; // element while (i < n && j >= 0) { if (mat[i][j] == x) { document.write( "n Found at " + i + " " + j); return ; } if (mat[i][j] > x) j--; else // if mat[i][j] < x i++; } document.write( "n Element not found" ); return ; // if ( i==n || j== -1 ) } // driver program to test above function let mat = [[10, 20, 30, 40 ], [ 15, 25, 35, 45 ], [ 27, 29, 37, 48 ], [ 32, 33, 39, 50 ]]; search(mat, 4, 29); // This code is contributed by bobby </script> |
输出
n Found at 2, 1
时间复杂性： O（n）。 只需要一次遍历，即i从0到n，j从n-1到0，最多2*n步。 上述方法也适用于mxn矩阵（不仅适用于nxn）。复杂性为O（m+n）。 空间复杂性： O（1）。 不需要额外的空间。
相关文章： 排序矩阵中的搜索元素 如果您发现上述代码/算法不正确，请写下评论，或者寻找其他方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
