优客文库提供全面的范文格式和文档模板,包括申请书、合同、借据、证明、求职信等,助力您快速撰写专业文档。

用java写一个算法:在一个 n * m 的二维数组中,每一行都按照从左到右 非递减 的顺序排序,每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断

来自 黑龙江省哈尔滨市 的网友 时间: 热度:°C 加入收藏 我要投稿 点赞()
可以使用二分查找的方法来判断二维数组中是否含有给定的整数。具体步骤如下:

1. 定义两个指针,一个指向二维数组的右上角元素,另一个指向左下角元素。
2. 比较指针指向的元素与目标整数的大小:
- 如果当前元素等于目标整数,返回 true。
- 如果当前元素大于目标整数,将指针向左移动一列。
- 如果当前元素小于目标整数,将指针向下移动一行。
3. 重复步骤 2,直到找到目标整数或者指针移动到二维数组的边界(超出数组范围)为止。
4. 如果找不到目标整数,返回 false。

以下是使用 Java 实现的代码示例:

```java
public class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}

int rows = matrix.length;
int cols = matrix[0].length;

int row = 0; // 行指针,从第一行开始
int col = cols - 1; // 列指针,从最后一列开始

while (row < rows && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
col--; // 向左移动一列
} else {
row++; // 向下移动一行
}
}

return false;
}
}
```

这个算法的时间复杂度为 O(n + m),其中 n 是二维数组的行数,m 是二维数组的列数。
221381
领取福利

微信扫码领取福利

微信扫码分享