一、题目描述
此题源于《剑指 offer》
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
输入:
[
[1, 2, 8, 9],
[4, 7, 10, 13]
],7
输出: true
二、思路分析
此题与前文二维数组检索 search-a-2d-matrix类似,与前文稍有不同,前文题目中每一行的第一个数字都比上一行最后一个数字大,这个条件保证了数组有序是单向的(此处的单向指的是一个方向的递增),但是此题难度稍微加剧,数组递增是向右向左递增,左右递增没有关系(可以理解为双向有序)。
解题技巧在于化双向为单向,如果同时考虑两个方向的递增那么必然会加大复杂度。可以采用从右上角或者左下角开始检索。以左上角为例,左上角具有当前行最大,当前列最小的特征,一定程度保证了单向,简化问题复杂度,以下是详细步骤
- 以左上角为起点,开始检索。
- 如果左上角元素大于目标元素,则目标元素定不存在当前列,起点右移。
- 如果左上角元素小于目标元素,则目标元素定不存在当前行,起点下移。
- 重复以上2,3步骤,最终可以将元素确定到一列或者一行中,此时可采用二分查找完成检索。
三、参考代码
public class Solution {
public boolean Find(int target, int [][] array) {
int x = array[0].length - 1,y = 0;
while(x > 0 && y < (array.length - 1)){
if(array[y][x] == target) return true;
if(array[y][x] < target) y++;
if(array[y][x] > target) x--;
}
int mid,left,right;
if(x == 0){
left = y;
right = array.length -1;
while(left <= right){
mid = left + (right -left)/2;
if(array[mid][0] == target) return true;
if(array[mid][0] > target) right = mid - 1;
if(array[mid][0] < target) left = mid + 1;
}
}else{
if(y == array.length - 1){
left = 0;
right = x;
while(left <= right){
mid = left + (right -left)/2;
if(array[y][mid] == target) return true;
if(array[y][mid] > target) right = mid - 1;
if(array[y][mid] < target) left = mid + 1;
}
}
}
return false;
}
}
四、测试连接
牛客网算法测试连接
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)