剑指:二维数组中的查找
题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
解:
可以从左下角或右上角开始找。
这里从左下角:
从左下角元素往上查找,右边元素是比这个元素大,上边是的元素比这个元素小。于是,target比这个元素小就往上找,比这个元素大就往右找。如果出了边界,则说明二维数组中不存在target元素。
public class Solution { public boolean Find(int target, int [][] array) { if(array == null) return false; int rows = array.length; int cols = array[0].length; int i=rows-1, j=0; //左下角元素左标 while(i>=0 && j<cols){ if(target < array[i][j]) i--; //查找的target小,往上找 else if(target > array[i][j]) j++; //查找的target大,住右找 else return true; //找到 } //出界,未找到 return false; } }
从二维数组的右上方开始查找:
- 若元素值等于
target
,返回true
; - 若元素值大于
target
,砍掉这一列,即--j
; - 若元素值小于
target
,砍掉这一行,即++i
。
package demo; public class FindPartiallySMatrix { public static boolean findn(int[][] arr, int target){ if(arr == null) return false; int rows = arr.length; int cols = arr[0].length; int i=0, j=cols-1; //从右上角开始找 while(i<rows && j>=0){ if(arr[i][j] == target) return true; if(arr[i][j] < target) i++; //行向下加 else j--; //列向左减 } return false; } public static void main(String[] args) { int[][] array = { {1,2,8,9}, {2,4,9,12}, {4,7,10,13}, {6,8,11,15} }; boolean result = findn(array, 10); System.out.println(result); } }
时间复杂度:O(m+n)