首页 > 试题广场 > 二维数组中的查找
[编程题]二维数组中的查找
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

333个回答

添加回答
推荐
/* 思路
* 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,
* 因此从左下角开始查找,当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时,上移
*/

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 回复(173)
package kewai; import java.util.Scanner; public class Base { public static void main(String[] args){ int a[][]={{1,2,3,4},
                   {2,3,4,5},
                {3,4,5,6},
                {4,5,6,7}};
        System .out.printf("请输入需要查询的数字:");
       Scanner i=new Scanner(System .in) ; int i1=i.nextInt() ; int j=3,j1=0; while(a[j][j1]!=i1){ if(a[j][j1]<=i1){
               j1=j1+1;
           }else if(a[j-1][j1]>=i1){
               j=j-1;
           }
       } if(a[j][j1]==i1){
            System .out.println("输入存在!该位置是:("+j+","+j1+").数值为:"+a[j][j1]) ;
        }
    }
}
发表于 今天 15:37:07 回复(0)
先定义到左下角,与目标数比较,若目标数大则删除列,若目标数小,则删除行。

发表于 2019-03-23 16:54:15 回复(0)
找数组的左下角或者右上角,对左下角,上边元素小于它,右边元素大于它,每次判断大小确定遍历方向,就不用把数组中的元素都遍历一遍了。
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
        row--;
    }
    return false;
    }
}

发表于 2019-03-20 22:12:00 回复(0)
就是对数组进行一个遍历,查看target存不存在与数组中

发表于 2019-03-20 21:48:39 回复(1)
import static java.util.Arrays.binarySearch;
public class Solution {
    public boolean Find(int target, int [][] array) {
        for (int[] arr : array) {
            int res = binarySearch(arr, target);
            if (res >= 0){
                return true;
            }
        }
        return false;
    }
}

直接对每一维数组用二分查找……

发表于 2019-03-19 22:30:34 回复(0)
public boolean Find(int target,int[][] array){
        int i = array.length - 1, j = 0;
        boolean flag = false;
        
        //System.out.println("初始 " + i + "  " + j);
        while(!flag && i >= 0 && j <= array[0].length - 1 ){
            if(array[i][j] == target){
                flag = true;//find
                continue;
            }else if(array[i][j] > target){
                i--;
                //System.out.println(" " + i + "  " + j);
                continue;
            }else if(array[i][j] < target){
                j++;
                //System.out.println(" " + i + "  " + j);
                continue;
            }
        }
        return flag;
}
发表于 2019-03-19 22:10:22 回复(0)
1.观察数组;
2.直接根据左下角进行判断
3.如果左下角的数字比目标数字大,就向上移,如果小,就向右移
public class Solution {
    public boolean Find(int target, int [][] array) {
        int m =array.length-1;
        int n=array[0].length;
        int i=0;
        while(m>=0&&i<n){
             if(array[m][i]>target) {
                    m--;
             } else if(array[m][i]<target) {
                 i++;
             } else {
                 return true;
             }
        }
        return false;

发表于 2019-03-19 17:29:24 回复(0)
最简单的方法,循环遍历数组,作比较:
public boolean Find(int target, int[][] array) {
   for (int i = 0; i < array.length; i++) {
      for (int j = 0; j < array[i].length; j++) {
         int temp = array[i][j];
         if (temp == target) {
           return true;
         }
           }
   }
   return false;
}

发表于 2019-03-19 17:15:34 回复(0)

class Solution {
public boolean Find(int target, int [][] array) {
boolean flag = false;
//获取数组长度,防止长度为0
int arrayV_length = array.length;
if (arrayV_length > 0 && array[0].length > 0) {
int arrayH_length = array[0].length;
//循环一维
for (int i = 0; i < arrayV_length; i++){
//因为数组是按顺序
//添加这个判断是为了可以减少循环次数
if (array[i][array[0].length-1] >= target && array[i][0] <= target) {
//进入二维
for (int j = 0; j < array[0].length; j++){
if (array[i][j] == target) {
flag = true;
break;
}
}
}
}
}
return flag;
}
}

发表于 2019-03-19 15:50:06 回复(0)
//暴力求解,哈哈
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 (array[i][j] == target) {  return true;
            }
        }
    }  return false;
}

发表于 2019-03-16 22:22:04 回复(0)
思路:
        二维数组是多个一维数组组成的,每个数组构成一列
        做一个循环,每次循环对一列数做二分查找

import java.util.Arrays;
public class Solution {
    public boolean Find(int target, int [][] array) {
        int i,flag;
        while(true){
            i=array.length;
            for(int j=0;j<i;j++){
                flag=Arrays.binarySearch(array[j],target);
                if(flag>=0)
                    return true;
            }
            return false;
        }
    }
}

发表于 2019-03-16 22:09:58 回复(0)
public class Solution {
  public boolean Find(int target, int [][] array) {
        boolean isFind = false;
        int rows = array[0].length,columns = array.length;
        if(array!=null&&rows>0&&columns>0){
            int row = 0;
            int column = columns-1;
            while(row<rows && column>=0){
                if(array[row][column]==target){
                    isFind = true;
                    break;
                }else if(array[row][column]>target){
                    column--;
                }else{
                    row++;
                }
            }
        }
        return isFind;
    }
}

首先选取数组中右上角的数字。如果该数字等于要查找的数字,查找过程结束;

如果该数字大于要查找的数字,剔除这个数字所在的列;

如果该数字小于要查找的数字,剔除这个数字所在的行。

也就是说如果要查找的数字不在数组的右上角,

则每一次都在数组的查找范围中剔除一行或者一列,

这样每一步都可以缩小查找的范围,直到找到要查找的数字,或者查找范围为空。

发表于 2019-03-15 13:03:51 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int m = array.length;
        int n = array[0].length;
        if(m==0||n==0||array[0][0]>target||array[m-1][n-1]<target)
        {
            return false;//边界值检测
        }
        for (int i = m - 1; i >= 0; i--) {
            int j = 0;//从左下角开始检测
            if(array[i][j]>target)
            {
                continue;
            }
            while(array[i][j]<target&&j<n)
            {
                j++;
            }
            if(array[i][j]==target)
            {
                return true;
            }
        }
        return false;
    }
}

要注意下数组越界问题,这是我第一次做题,做的不好轻喷
发表于 2019-03-15 12:13:51 回复(0)
不用担心array数组是空的吗?array.length可能异常啊?
发表于 2019-03-15 11:08:17 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
            boolean result = false;
            int colms = array[0].length;
            if(colms==0)
                return false;
            int rows = array.length;
            for(int i=0;i<rows;i++){
                if(array[i][0] <= target && target <= array[i][colms-1]){
                    if(binarySearch_arrray(array[i],target)){
                        result = true;
                        break;
                    }
                }
            }
        return result;
    }
    
    public boolean binarySearch_arrray(int[] array,int target){
        int r = array.length-1;
        int l = 0;
        while(r>=l){
            int mid = (r+l)/2;
            if(array[mid]>target)
                r = mid-1;
            else if(array[mid]<target){
                l = mid+1;
            }else{
                return true;
            }
        }
        return false;
    }
}

编辑于 2019-03-13 17:40:58 回复(0)
参照一维数组的二分查找,不同的是当取的中点mid的值不等于target时,余小的二维数组可以被mid分为四块,要在其中的三小块递归查询。
此方法的时间复杂度小于标准答案的n^2,为  n^(log2 3), n为一维数组的长度
public class Solution {
    public boolean Find(int target, int [][] array) {
        return Find( target, array, 0, 0, array.length-1, array[0].length-1);
    }
    
    private boolean Find(int target, int [][] array, int firstx, int firsty, int lastx, int lasty) {
        if(firstx>lastx || firsty>lasty){
            return false;
        }else{
            int midx = (firstx+lastx)/2;
            int midy = (firsty+lasty)/2;
            if(array[midx][midy]==target){
                return true;
            }else if(lastx==firstx && lasty==firsty){
                return false;
            }else if(target<array[midx][midy]){
                return Find(target,array,firstx,firsty,midx-1,midy-1)||
                    Find(target,array,firstx,midy,midx-1,lasty)||
                    Find(target,array,midx,firsty,lastx,midy-1);
            }else{
                return Find(target,array,midx+1,midy+1,lastx,lasty)||
                    Find(target,array,midx+1,firsty,lastx,midy)||
                    Find(target,array,firstx,midy+1,midx,lasty);
            }
        }
    }
}

发表于 2019-03-13 16:09:49 回复(0)
可以用二分法解决这道题,由于每一行,每一列都是有序排列的,那么,我们可以从第一列开始一步一步的遍历,对于每一列采用二分查找,可以快速找到是否存在
public boolean Find(int target, int [][] array) {
        for(int i=0;i<array.length;i++) {
            int carryrow=0,carryline=array[0].length-1;
            while(carryrow<=carryline) {
                int mid=(carryrow+carryline)/2;
                if(array[i][mid]==target)
                    return true;
                else if(array[i][mid]>target)
                    carryline=mid-1;
                else
                    carryrow=mid+1;
            }
            
        }

        return false;
    }

发表于 2019-03-12 10:18:41 回复(0)
1.判断是否为null或者长度是否为0,满足直接返回空
2.双for循环直接比较,满足跳出,在for循环外部判断和目标数字是否相同,相同存在以下情况:
    1.要查找的数字直接在最后一位,返回true
    2.否则直接返回false
不同直接返回true
发表于 2019-03-11 17:25:22 回复(0)
时间复杂度O(m+n),空间复杂度O(1)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int n = array.length;
        int m = n == 0 ? 0 : array[0].length;
        int i = 0, j = m - 1;
        while (i < n && j >= 0) {
            if (target > array[i][j]) i++;
            else if (target < array[i][j]) j--;
            else return true;
        }
        return false;
    }
}

发表于 2019-03-11 15:43:42 回复(0)
//通过第i行第1列的值和target比较,当target<array[i][0]时,与target相同的整数只会出现在i-1行
//通过第i行最后一列的值和target比较,当target<array[i][array[0].lengh-1]时,只需要遍历第i行
public class Solution {
    public boolean Find(int target, int [][] array) {
        int n = array.length;
        if(n <= 0 || array[0].length == 0)
            return false;
        for(int i = 0; i < n; i++){
            if(target < array[i][0] && i!=0 || i == n-1){
                for(int j = 0; j < n; j++){
                    if(target == array[i-1][j])
                        return true;
                }
            }
             if(target <= array[i][n-1]){
                 for(int j = n-1; j >= 0; j--){
                     if(target == array[i][j])
                         return true;
                 }
             }                
        }
        return false;
    }
}
发表于 2019-03-08 21:55:54 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号