欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指 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;
    }
};

代码写都有些混乱,说明我的逻辑有缺陷,以后也会慢慢改进。
看到别人的代码更简单:从左下方开始遍历,比目标点大则向上走,小则向又走,代码又短思路又清晰,真棒。