首页 > 试题广场 > 二维数组中的查找
[编程题]二维数组中的查找
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
推荐
/* 思路
* 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,
* 因此从左下角开始查找,当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时,上移
*/

class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        int rowCount = array.size();
        int colCount = array[0].size();
        int i,j;
        for(i=rowCount-1,j=0;i>=0&&j<colCount;)
        {
            if(target == array[i][j])
                return true;
            if(target < array[i][j])
            {
                i--;
                continue;
            }
            if(target > array[i][j])
            {
                j++;
                continue;
            }
        }
        return false;
    }
};

编辑于 2015-06-18 16:50:07 回复(199)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int row = 0;
        int col = array[0].length - 1;
        while (col>=0 && row<array.length) {
            if (array[row][col] > target) {
                col--;
            } else if(array[row][col] < target){
                row++;
            } else {
                return true;
            }
        }
        return false;
    }
}
由于数组是有序的,所以可以从左上角开始查找,当数组元素大于target时,减小一列,当数组元素小于target时,增加一行,相等时直接返回true,如果没有该值,退出while循环时返回false。
编辑于 2019-07-22 20:48:52 回复(0)
    public boolean Find(int target, int [][] array) {
        for(int i[]: array){
            for(int j:i){
                if(target==j){
                    return true;
                }
            }
        }
        return false;
    }
}
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        for i in array:
            for j in i:
                if target == j:
                    return True
        return False
        # write code here

编辑于 2019-07-22 00:56:23 回复(1)
/*
时间限制:1秒 空间限制:32768K 热度指数:1208017
本题知识点: 查找 数组
题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
*/

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(target > array[i][array[i].length - 1] || target < array[i][0]) {
                    break;
                } 
                if (target == array[i][j]) {
                    return true;
                }
            }
            
        }
        return false;
    }
}


发表于 2019-07-17 08:22:22 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array[0].length == 0){
            return false;
        }
        for(int i = 0;i<array.length;i++){
            for(int j = 0;j<array.length;j++){
                if(target<array[i][j]) {
                    break;
                }else if(target == array[i][j]){
                    return true;
                }
            }
        }
        return false;
    }
}

发表于 2019-07-16 12:54:14 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
    int array_h = array.length;
        int x=0;
    if(array_h==0) return false;
        for(int h=0;h<array_h;h++){
            for(int l=0;l<array[0].length;l++){
                if(target==array[h][l])
                 x=1;
            }
        }
        if(x==1)
            return true;
        else
            return false;
    }
}
遍历二维数组,如有相等,令变量x取1,否则取0;最后判断x取值,最终返回false 或 true

发表于 2019-07-14 17:53:17 回复(0)




int row = 0; //行 
int col = array[0].length - 1; //列 
while (row < array.length && col >= 0){ 
if (array[row][col] > target){
    col--; }else if (array[row][col] < target)
{
      row++;
    }else { return true;
    }
} return false;

编辑于 2019-07-12 17:12:59 回复(0)
解题思路写在代码注释里:需要注意数组长度为0的情况
public class Solution {
    public static boolean Find(int target, int [][] array) {
        //右上角开始判断:array[row][column]
        //如果该数大于每一行的最后一个元素,就给行数加row++;
        //如果小于,就列数减column--;
        int n = array[0].length;
        if(n == 0)
            return false;
        for(int i = 0;i < n; i++){
            if(array[i][n - 1] == target)
                return true;
            for(int j = 0;j < array[i].length; j++){
                if(array[i][j] == target)
                    return true;
            }
        }
        return false;
    }
    public static void main(String[] args){
        int [][]array = {{1,4,8,9},{2,5,9,12},{6,9,14,16}};
        if(Find(14,array)){
            System.out.println("数组中存在该整数!");
        }
        else
            System.out.println("数组中不存在该整数!");
    }
}
发表于 2019-07-10 10:40:57 回复(0)

首先排除空的情况,然后从4个方向逐渐逼近,直到找到就成功或者就剩最后一个数就失败

public class Solution {
public boolean Find(int target, int [][] array) {
int len = array.length - 1;
if (len < 0)
return false;
int ylen = array[0].length - 1;
if (ylen < 0)
return false;
if (target array[len][ylen])
return false;
int x_min = 0;
int x_max = len;
int y_min = 0;
int y_max = ylen;
while (true) {
while (array[x_max][y_min] > target && x_max > x_min)
x_max--;
while (array[x_min][y_max] x_min)
x_min++;
while (array[x_min][y_max] > target && y_max > y_min)
y_max--;
while (array[x_max][y_min] y_min)
y_min++;
if (array[x_max][y_min] == target)
return true;
if (x_min == x_max && y_max == y_min) {
return false;
}
}

}

}

发表于 2019-07-05 14:46:47 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array==null||array.length==0)return false;
        int row=array.length-1;
        int col=0;
        while(col<array[0].length&&row>=0){
            if(array[row][col]==target)return true;
            else if(array[row][col]>target) row--;
            else col++;
        }
        return false;
    }
}

发表于 2019-07-04 20:35:38 回复(0)
也是一种遍历查找,只不过是依据矩阵的特性进行遍历。
因为矩阵是从左到右递增以及从上到下递增的,所以我们可以从第一行的最后一列的数据开始遍历,设为m。如果m等于target则直接返回true,若m小于target,则意味着m所在行的左边的数据均为小于target的,所以此时只需要跳到下一行的同一列继续查询。若m大于target则意味这m所在这一列往下均大于target,所以只需跳到m所在列的左边一列进行查询即可。代码如下:
         int i = 0;
        int j;
        int row = array.length;
        int col = array[0].length;
        j = col-1;
        while(i<row&&j>=0)
        {
            if(array[i][j]<target)
            {
                ++i;
            }
            else if(array[i][j]==target){
                return true;
            }else
            {
                --j;
            }
        }
        return false;
发表于 2019-07-01 16:48:45 回复(0)
public static boolean Find(int target, int [][] array) {
        int i = 0;
        int j = array[0].length-1;
        while(i=0)
        {
            if(array[i][j]==target)
            {
                return true;
            }
            else if(array[i][j]<target)
            {
                i++;
            }
            else
            {
                j--;
            }
        }
        return false;
    }

要点:

  • 考虑到从左到右从上到下递增,所以可以从从右上角开始找,比目标大就往下走,比目标小就往左走,知道超出边界。
  • 时间复杂度分析 暴力遍历O(n*m)-->现在的方法O (n+m),n,m分别表示行数和列数
  • 可以优化的地方 在while循环外面可以加上以下条件,在特殊情况下会快点。
    if(target>array[array.length][array[0].length]){
    return false;}
    if(target==array[array.length][array[0].length]){
    return true;}
       while...
编辑于 2019-06-25 13:55:53 回复(0)
我这样可以通过测试
public class Solution {
    public boolean Find(int target, int [][] array) {
        int i,j;
        boolean k=false;
        for(i=0;i<array.length;i++){
            for(j=0;j<array[0].length;j++){
               if (array[i][j]==target){
                   k=true;
                   break;
               }
            }
        }
        return k;
    }
}
发表于 2019-06-20 21:35:54 回复(0)
     public static boolean Find(int target, int [][] array) {                       int row = array[0].length;              int col = array.length;              if(array==null||row==0||col==0)                  return false;                            if(target<array[0][0]||target>array[col-1][row-1]){                  return false;              }                        for(int i=0;i<col;i++){                  for(int j=0;j<row;j++){                      if(target==array[i][j])                          return true;                  }              }                                           return false;                                                   }      



发表于 2019-06-19 09:41:12 回复(0)
public boolean Find(int target, int [][] array) {
        if(array == null) return false;
        if(array[0].length == 0) return false;
  
  int len = array.length;
  int line = len - 1;
  int rows = 0;
  
  while(line >= 0 && rows <= len - 1)
  {
   if(array[line][rows] == target) return true;
   else if(array[line][rows] > target) line--;
   else if(array[line][rows] < target) rows++;
  }
  
  return false;
    }
发表于 2019-06-11 14:11:49 回复(0)
/**例子:
在下面的数组中找 7 
*   
* {1, 2, 4,  5}, 
* {2, 4, 5,  8},  
* {4, 7, 10, 13},  
* {6, 8, 11, 15} 
*   
*   
* 思路:数组的行列都是有序的,使用二分查找。  
* 先确定目标数据 7 可能落在的行,对第一列进行二分查找,
如果直接命中了,则返回对应的下标,如果没有命中,则返回目标可能在的那一列的下标的负数再减去1 ,  
* 减去1 的目的为了区别,第一个元素就是目标,0 的负数 还是 0 ,无法区别,因此减去1;  
*   
* 然后对对应列进行二分查找,只需要查找一列即可,因为下一列的起始数据比目标大,不给予考虑 ;  
*   
* 对行的处理有点不同,我们对最后一列进行二分查找,确定数据可能落在的行,只要是比目标数据小的行 都有可能,不像列那么简单只有一列可能 。  
*   
* 因此,我们根据列与行之间确定一个区间,对区间内的每一行都进行二分查找即可。  
*   
* 这这里对首列进行二分判断的时候,得到的下标是 3 ,对最后一列进行二分查找 得到的下标是 1 ,因此,只需要对 第 2,3 4 行进行二分查找即可。  
*   
*   
* 思路很简单,大概就是这么个意思,可能描述的不好,就是确定区间进行二分找;  * 还有一个就是确定边界,做了许多检测,才通过这道题。  
*   
* 对了,不要不确定区间,就直接二分查找,那样很傻。剪枝一下,可以排除大部分没有的行。  
* * @author yiaz 
* @date 2019/6/6 
* @description 忽略中文类名  
*/
public class 二维数组中的查找 { public boolean find(int target, int[][] array) { if (array == null || array.length == 0 || array[0].length == 0) { return false; } // 确定目标数据可能存在的列下标 int firstIndex = binarySearch(target, array, 1, 0); int lastIndex = binarySearch(target, array, 2, 0); // 判断是否直接命中 if (firstIndex >= 0 || lastIndex >= 0) { return true; } // 判断是否不再界限内 if (firstIndex == -array.length - 1 || lastIndex == -array.length - 1) { return false; } // 都没有命中,则进行对目标可能存在的列进行二分查找 int firstTarget = binarySearch(target, array, 3, -firstIndex - 1); if (firstTarget > 0) { return true; } for (int i = -lastIndex - 1; i < -firstIndex - 1; i++) { int num = binarySearch(target, array, 3, i); // 此处不需要等于0,如果等于0 ,则表示没查到,要是等于0 是查到,则属于直接命中,上文已经处理了 if (num > 0) { return true; } } return false; } /** * 二分查找目标数字可能存在的行列 * * @param target 目标数字 * @param array 数组 * @param flag 标记,思路中需要对 首列,末列 以及确定的区间进行二分查找,flag 标记是哪一种, 1 是 首列,2 是末列,3 是正常的行 * @param index 当对正常的行查找的时候,也就是 flag是3 的时候,index 表示从哪一行开始 * @return */ private int binarySearch(int target, int[][] array, int flag, int index) { int low = 0; int high = 0; int middle = 0; int targetIndex = 0; switch (flag) { case 1: case 2: // 末尾列查找 high = array.length - 1; break; default: // 正常查找 high = array[0].length - 1; } while (low <= high) { targetIndex = (high - low) / 2 + low; switch (flag) { case 1: // 确定边界 if (target < array[0][0]) { return -array.length; } // 首列查找 middle = array[targetIndex][0]; break; case 2: // 确定边界 if (target > array[array.length - 1][array[0].length - 1]) { return -array.length; } // 末尾列查找 middle = array[targetIndex][array[0].length - 1]; break; default: // 确定边界 if (target < array[index][0] || target > array[index][array[0].length - 1]) { return -array.length; } // 正常查找 middle = array[index][targetIndex]; } if (target == middle) { return targetIndex; } else if (target > middle) { low = targetIndex + 1; } else { high = targetIndex - 1; } } return -targetIndex - 1; } }
编辑于 2019-06-06 12:50:02 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        // 判断数组是否为空
        if ( array == null || array.length == 0 ) {
            return false;
        }
        // 循环遍历数组的每一行
        for ( int i = 0; i < array.length; i++ ) {
            //若该行数组为空则跳过
            if ( array[i].length == 0 ) {
                continue;
            }
            //若该行数组不为空则进行范围判定
            if (array[i][0] <= target && array[i][array[i].length - 1] >= target) {
                // 遍历范围中可能包含target的数组
                for ( int j = 0; j < array[i].length; j++ ) {
                    if ( array[i][j] == target ) {
                        return true;
                    }
                }
            // 避免后续的重复判断
            }else if ( array[i][0] > target ) {
                break;
            }
        }
        return false;
    }
}
发表于 2019-06-02 17:26:26 回复(0)
用哈希map一下就出来了。很easy,代码略。
发表于 2019-06-02 09:10:15 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int len = array.length-1;
        int i = 0;
        while((len>=0)&&(i<array[0].length)){
            if(array[len][i] < target){
                i++;
            }else if(array[len][i] > target){
                len--;
            }else{
                return true;
            }
        }
        return false;
    }
}

发表于 2019-05-30 20:04:49 回复(0)
//找出能++,--的分界点,左下,右上都可以
public class Solution {
    public boolean Find(int target, int [][] array) {
        int row = 0;
        int col = array[0].length-1;
        while(row <= array.length-1 && col >= 0){
            if(array[row][col] > target)
                col--;
            else if(array[row][col] < target)
                row++;
            else
                return true;
        }
        return false;
    }
}

发表于 2019-05-25 11:54:36 回复(0)
从矩阵右上角进行比较,target如果等于该值,返回该值,如果比该值大,下标就往下移row+1,如果比该值小,下标就往左移cols-1。
发表于 2019-05-22 12:41:24 回复(0)