java找出方阵中的马鞍数
时间: 2024-06-12 22:08:27 浏览: 12
马鞍点是指在一个矩阵中,某个元素既是其所在行的最小值,同时又是其所在列的最大值。根据引用中的描述,一个矩阵中至多只能有一个马鞍点。
关于如何找出方阵中的马鞍数,可以采用思路一或思路二。
思路一是最简单直接的方法,即对矩阵中的每一个元素进行判断,若该元素既是其所在行的最小值,同时也是其所在列的最大值,则该点为矩阵中的一个马鞍点。思路一的时间复杂度为O(N^3),其中N表示方阵的边长。示例代码如下:
```java
void saddlePoint_one(int[][] matrix) {
int ROW = matrix.length;
int COL = matrix[0].length;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
System.out.print(matrix[i][j] + "\t");
}
System.out.println();
}
boolean flag = true;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
int k = 0, temp = matrix[i][j];
flag = true;
for (k = 0; k < COL; k++) {
if (temp > matrix[i][k]) {
flag = false;
break;
}
}
for (k = 0; flag && k < ROW; k++) {
if (temp < matrix[k][j]) {
flag = false;
break;
}
}
if (flag) {
System.out.println("matrix[" + i + "][" + j + "] : " + matrix[i][j] + " 为马鞍数");
}
}
}
}
```
思路二是在思路一的基础上进行优化,使用一维数组分别保存每行的最小值和每列的最大值,然后再对每个元素进行判断。思路二的时间复杂度为O(N),其中N表示方阵的边长。示例代码如下:
```java
void saddlePoint_two(int[][] matrix) {
int ROW = matrix.length;
int COL = matrix[0].length;
int[] row_min = new int[ROW];
int[] col_max = new int[COL];
for (int i = 0; i < ROW; i++) {
row_min[i] = matrix[i][0];
for (int j = 1; j < COL; j++) {
row_min[i] = Math.min(row_min[i], matrix[i][j]);
}
}
for (int j = 0; j < COL; j++) {
col_max[j] = matrix[0][j];
for (int i = 1; i < ROW; i++) {
col_max[j] = Math.max(col_max[j], matrix[i][j]);
}
}
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (matrix[i][j] == row_min[i] && matrix[i][j] == col_max[j]) {
System.out.println("matrix[" + i + "][" + j + "] : " + matrix[i][j] + " 为马鞍数");
}
}
}
}
```