二维数组中的查找

二维数组中的查找

题目来源

牛客网

题目描述

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

解题思路

解法一：

判断一个二维数组中是否存在某一个元素，直接遍历：

public class Solution { public boolean Find(int target, int [][] array) { for(int i = 0;i < array.length;i++){ for(int j = 0;j<array[i].length;j++){ if(array[i][j] == target){ return true; } } } return false; } }

但是使用这种方式效率比较低下…

解法二：由于元素保存在二维数组当中是有规律的，每一行从左到右递增，每一列从上到下递增，所以从第一行的最后一个元素开始判断，如果小于当前值则像左找，否则向下找，直到元素遍历到左下角 还没有则返回false。 public class Solution { public boolean Find(int target, int [][] array) { int i = 0; //第一行 int j = array[0].length - 1; //最后一列 while (i < array.length && j >= 0) { if (array[i][j] > target) { j--; } else if (array[i][j] < target) { i++; } else { return true; } } return false; } }