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

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

剑指Offer

题目

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 矩阵如下: 1 2 8 9 2 4 9 12 4 7 10 3 6 8 11 15

解题思路

找规律 从右上角或者左下角找规律。 如果 查找的值大于右上角的值，向下搜索 如果 查找的值小于右上角的值，向左搜索 直到 等于右上角的值

二分法 因为每行有序 按每一行或每一列进行二分查找

代码实现 找规律

public class Solution { public boolean Find(int target, int [][] array) { if (array == null) { return false; } //行长 int rLength = array.length; if(rLength == 0) { return false; } //列长 int cLength = array[0].length; if(cLength == 0) { return false; } //如果大于右下角的,返回 if (array[rLength-1][cLength-1] < target){ return false; } if (array[0][0] > target) { return false; } //右上角节点的起始行数 int node = 0; //从右上角开始，从右向左遍历列 for (int i = cLength-1; i >= 0 ; i--) { //如果等于右上角的,返回 if (array[node][i] == target){ return true; } //值大于右上角，向下查找 if (target > array[node][i]) { for (int j = node ; j < rLength ; j++) { //找到 if (array[j][i] == target){ return true; } //节点下移 node++; if (target < array[j][i]) break; } } //值小于右上角的，顶点左移，向左继续搜素 } return false; }}

按列二分

public static boolean find(int[] a ,int left,int right,int target){ int mid = (left + right)/2; if (target == a[mid]||target == a[left]||target == a[right]) return true; if (left == right) return false; if (target < a[mid]) { find(a,++left,--mid,target); } if (target > a[mid]){ find(a,++mid,--right,target); } return false;}public static boolean Find2(int target, int[][] array) { if (array == null) { return false; } if(array.length == 0) { return false; } //列长 if(array[0].length == 0) { return false; } //如果大于右下角的,返回 if (array[array.length-1][array[0].length-1] < target){ return false; } if (array[0][0] > target) { return false; } for (int i = 0; i < array.length-1 ; i++) { if(find(array[i],0,array[i].length-1,target)){ return true; } } return false;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。