剑指 offer:二维数组中的查找
程序员文章站
2022-07-15 16:16:37
...
题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
分析:要充分利用数组的递增特点。我的思路:先将数组向右开始遍历,若失败,则改为向下,同时失败那点的右下方全都没必要再访问(因为都比失败的那个点大,也即比目标点大)。若向下遍历失败则向左,再向右,再向左(即只可能在左下方移动,因为左上方的点都比已经查找的点小,即比目标点小,也没必要再访问)。
代码如下:
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int i = 0;
int j = 0;
if (i < array.size() && j < array[0].size() && array[i][j] == target) {
return 1;
}
if (i < array.size() && j < array[0].size() && array[i][j] < target) {
//向右走
while (j < array[0].size() && array[i][j] < target) {
j++;
}
if (j < array[0].size() && array[i][j] == target) {
return 1;
}
j--;
i++;
//向左下方走
while (j >= 0 && i < array.size()) {
if (array[i][j] == target) {
return 1;
}
if (array[i][j] < target) {
i++;
}
else {
j--;
}
}
}
return 0;
}
};
代码写都有些混乱,说明我的逻辑有缺陷,以后也会慢慢改进。
看到别人的代码更简单:从左下方开始遍历,比目标点大则向上走,小则向又走,代码又短思路又清晰,真棒。
上一篇: 剑指offer——二维数组中的查找
下一篇: D-有趣的数字
推荐阅读
-
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指offer28:找出数组中超过一半的数字。
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
C#版剑指Offer-001二维数组中的查找
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
剑指offer JZ31 整数中1出现的次数 Python 解
-
剑指offer JZ54 字符流中第一个不重复的字符 Python 多解
-
剑指Offer积累-JZ1-二维数组中的查找
-
剑指offer之队列中的最大值(C++/Java双重实现)
-
剑指offer之在排序数组中查找数字 I(C++/Java双重实现)