两种思路 一种是: 把每一行看成有序递增的数组, 利用二分查找, 通过遍历每一行得到答案, 时间复杂度是nlogn public class Solution { public boolean Find(int [][] array,int target) { for(int i=0;i<array.length;i++){ int low=0; int high=array[i].length-1; while(low<=high){ int mid=(low+high)/2; if(target>array[i][mid]) low=mid+1; else if(target<array[i][mid]) high=mid-1; else return true; } } return false; } } 另外一种思路是: 利用二维数组由上到下,由左到右递增的规律, 那么选取右上角或者左下角的元素a[row][col]与target进行比较, 当target小于元素a[row][col]时,那么target必定在元素a所在行的左边, 即col--; 当target大于元素a[row][col]时,那么target必定在元素a所在列的下边, 即row++; public class Solution { public boolean Find(int [][] array,int target) { int row=0; int col=array[0].length-1; while(row<=array.length-1&&col>=0){ if(target==array[row][col]) return true; else if(target>array[row][col]) row++; else col--; } return false; } }
# -*- coding:utf-8 -*- class Solution: # array 二维列表 def Find(self, target, array): # write code here rows = len(array) - 1 cols= len(array[0]) - 1 i = rows j = 0 while j<=cols and i>=0: if target<array[i][j]: i -= 1 elif target>array[i][j]: j += 1 else: return True return False
class Solution { public: bool Find(int target, vector<vector<int> > array) { // array是二维数组,这里没做判空操作 int rows = array.size(); int cols = array[0].size(); int i=rows-1,j=0;//左下角元素坐标 while(i>=0 && j<cols){//使其不超出数组范围 if(target<array[i][j]) i--;//查找的元素较少,往上找 else if(target>array[i][j]) j++;//查找元素较大,往右找 else return true;//找到 } return false; } };
public class Solution { public boolean Find(int target, int [][] array) { 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--; else if(target>array[i][j]) j++; else return true; } return false; } }
class Solution { public: bool Find(vector<vector<int> > array,int target) { int m,n,x,y; m = array.size();//行数 n = array[0].size();//列数 x=m-1;y=0;//坐标定在左下角 while(x>=0 && y<=n-1){ if(target<array[x][y]){ x--;//遇小上移 } else if(target>array[x][y]){ y++;//遇大右移 } else { return true; } } return false; } };
其实也可以从右上开始寻找; class Solution { public: bool Find(vector<vector<int> > array,int target) { int row = array.size(); int col = array[0].size(); int i,j; for (i=0,j=col-1;i<row && j>=0;) { if (array[i][j] == target) { return true; } if (array[i][j] > target) { j--; continue; } if (array[i][j] < target) { i++; } } return false; } };
<?php
function Find($target, $array)
{
// write code here
$rows = count($array);//行
$columns = count($array[0]);//列
$rs = false;
//从右上角开始,
for ($row = 0,$column = $columns - 1; $row < $rows && $column >= 0;) {
if($array[$row][$column] == $target){
$rs = true;
break;
}
if ($array[$row][$column] > $target){
//大于目标数,剔除本列
$column--;
}
if($array[$row][$column] < $target) {
$row++;
}
}
return $rs;
}
public class Solution { public boolean Find(int target, int [][] array) { boolean flag = false; int x=0; int y=0; for(int i=0;i < array.length;i++) { for(int j=0;j<array[i].length;j++) { if(target==array[i][j]){ flag = true; break; } } } if(flag) { System.out.println("exist!"+target+",location:"+"array["+x+"]["+y+"]"); } return flag; } }
class Solution { public: bool Find(vector<vector<int> > array, int target) { int Row = array.size(); int Col = array[0].size(); for (int i = 0, j = Col-1; i < Row && j >=0;) { if (target > array[i][j]) i++; else if (target < array[i][j]) j--; else if (target == array[i][j]) return true; } return false; } }; 从左下角或者右上角开始搜索均可
public class Solution { public boolean Find(int target, int [][] array) { if(array == null || array[0].length == 0){ return false; } for(int i = 0;i < array.length;i++){ int head = 0; int tail = array[i].length-1; while(head<=tail){ int mid = (head+tail)/2; if(target < array[i][mid]){ tail = mid - 1; } else if(target > array[i][mid]){ head = mid + 1; } else return true; } } return false; } }
从右上角开始,因为左边比它小,右边比它大,如果当前值比target小就 行数+1,如果当前值比target小就 列数-1,最后保证不越界就好。
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int i=0;
int j=array[0].size()-1;
while(i<array.size()&&j>=0){
if(array[i][j]==target)
return true;
if(array[i][j]<target)
i++;
else if(array[i][j]>target)
j--;
}
return false;
}
};
看了很多解法都把二维数组当做矩阵,根本没考虑不等长的问题(好吧,按题意“每一列都按照从上到下递增的顺序排序”,应该不用考虑);
例如以下测试案例,那些解法就过不了:
target = 12;
int[][] array =
{{1,2,8},{2,4,9,12},{4,7},{6,8,11,15}};
public class Solution { public boolean Find(int target, int [][] array) { int r=array.length-1,c=0,maxCol=0; for (int i=0;i<=r;i++) if (array[i].length>maxCol)maxCol=array[i].length;//元素最多的一行,元素数量为maxCol while (r>=0&&c<maxCol){ if (c >= array[r].length)r--; //若该行元素较少,不存在第c列元素,继续上移; else if (array[r][c]<target)c++; else if (array[r][c]>target)r--; else if (array[r][c]==target)return true; } return false; } }
当然,对每一行进行二分查找或者暴力搜索不存在此问题;
以有序矩阵的左下角或者右上角为起点。
这样比较可以根据大小确定遍历的方向。
public class Solution { public boolean Find(int target, int [][] array) { int row = array.length-1; int col = 0; while(row>=0&&col<=array[0].length-1){ if(target==array[row][col]){ return true; }else if(target>array[row][col]){ col++; }else if(target<array[row][col]){ row--; } } return false; } }
扫一扫,把题目装进口袋
扫描二维码,进入QQ群
扫描二维码,关注牛客网公众号