二维数组的查找(每一行每一列都是递增顺序)?

小半 • 2023年2月10日下午5:00 • Java • 阅读 196

问题描述:
在一个二维数组中( 每个一维数组的长度相同)，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
要求时间复杂度(O(M+N),空间复杂度O(l)
解题思路:该二维数组中的一个数，它左边的数都比它小，下边的数都比它大。因此，从右上角开始查找，就可以根据num和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。
代码如下:

public class SelelctArray {
	public boolean find(int num, int[][]matrix) {
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
			return false;
		}
		int rows = matrix.length, cols = matrix[0].length;
		int r = 0,c = cols - 1;//从右上角开始
		while (r <= rows - 1 && c >= 0) {
			if (num == matrix[r][c]) {
				return true;
			} else if (num > matrix[r][c]) {
				r++;
			} else {
				c--;
			}
		}
		return false;
	}
	public static void main(String[] args) {
		int num = 20;
		int[][] matrix = {
				{1,4,7,11,15},
				{2,5,8,12,19},
				{3,6,9,16,22},
				{10,13,14,17,24},
				{18,21,2326,30},
		};
		SelelctArray a = new SelelctArray();
		boolean b = a.find(num, matrix);
		System.out.println(b);
	}
}

笔者刚开始运营公众号啦，感兴趣的可关注我的公众号，欢迎交流！