【剑指offer】面试题4-二维数组中的查找

题目：

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

1.思路

（1）获取数组的长和宽

以二维数组右上角或者左下角元素作为标志位进行遍历（这里以右上角举例）。

（2）遍历并比较判断

①若右上角元素值与目标值target相等，返回true；
②若右上角元素值大于（>）目标值taiget，则令遍历数组的列下标减1；
原因：当前右上角元素所在的列可以全部被忽略，以后不再遍历，因为这一列的元素值肯定都比target大，搜索区域减少一列。
③若右上角元素值小于（＜）目标值taiget，则令遍历数组的行下标加1。
原因：当前右上角元素所在的行可以全部被忽略，以后不再遍历，因为这一行的元素值肯定都比target小，搜索区域减少一行。

2.代码（Java实现）

public class Solution {
    public boolean Find(int target, int [][] array) {
        int col = array.length;		//获取列数
		int row = array[0].length;	//获取行数
		int i = col - 1;			//设置遍历的起始列下标
		int j = 0;					//设置遍历的起始行下标
		//System.out.print(col + " " + row);
		while(i >=0 && j < row) {	//下标合法性判断
			if(target == array[i][j]) {	//匹配
				return true;
			}else if (target >= array[i][j]) {
				j ++;				//行数+1
			}else if (target <= array[i][j]) {
				i --;				//列数-1
			}
		}
		return false;
    }
} // O(m+n)

PS:苏州大学考研真题，有一年考过这个题

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/88e3e437.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。