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

268个回答

添加回答
推荐
/* 思路
* 矩阵是有序的
   查看全部
编辑于 2015-06-18 16:50:07 回复(150)
/*两种方法:
第一种思路:对每一行进行二分查询,假设有n*m的矩阵,则时间复杂度是O(n*log(m)),编写代码的时候可以相应进行剪枝缩小时间复杂度;
第二种思路:观察矩阵可以知道,到我们取左下角作为根节点,可以将矩阵看做是一个二叉排序树,向上值减小,向右值增大,这样问题便转化为对二叉排序树的查询,令m>n,平均复杂度经演算大致为O(n^2);*/
public class Solution {
    public boolean Find(int target, int [][] array) {
        int high = array[0].length - 1;
        for(int i=0; i < array.length; ++i){
            int low = 0;
            while(low <= high){
                int mid = (low + high)/2;
                if(array[i][mid] < target){
                    low = mid + 1;
                }else if(array[i][mid] > target){
                    high = mid - 1;
                }else
                    return true;
            }
        }
        return false;
    }
}
发表于 2018-10-19 15:31:12 回复(0)

从左上角开始先按行比较,当target小于或等于当前值时,则判断是否相等,是则返回true,否则将当前值的列坐标设为内循环终止条件,跳出内循环,进行下一行的判断。

Java:

```
public class Solution {
    public boolean Find(int target, int [][] array) {
        int rows = array.length;
        int cols = array[0].length;
        for(int j = 0;j<rows;j++){
            for(int i = 0;i<cols;i++){
                if(target<=array[j][i]){
                    if(target==array[j][i])
                       return true;
                    else{
                        cols = i; 
                    }    
                }
           }
        }
        return false;
    }
}

python:

# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
    # write code here
    rows = len(array)
    cols = len(array[0])
    for j in range(rows):
        for i in range(cols):
            if target<=array[j][i]:
                if target == array[j][i]:
                    return True
                else:
                    cols = i
    return False

编辑于 2018-10-15 22:11:57 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int row=array.length;
        int column=array[0].length;
        int i=row-1;
        int j=0;
        while(i>=0 && j<column){
            if(array[i][j]==target){
                return true;
            }else if(array[i][j]>target){
                i--; //从右下角开始,如果i行的第一个数比target大,则到前一行
            }else{
                j++;//如果不相等,且当前的array[i][j]比target小,则j移到下一个
            }
        }
        return false;
    }
}
发表于 2018-10-11 03:51:35 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
                int i = 0, j = array[0].length - 1;
        while (i < array.length && j >= 0) {
            if (target > array[i][j]) {
                i++;
            } else if (target < array[i][j]) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }
}

发表于 2018-10-02 11:30:45 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int row = array.length;
        int col = array[0].length;
        int i = 0;
        int j = col - 1;
        while (i < row && j >= 0) {
            if (array[i][j] > target) {
                j --;
            }
            else if (array[i][j] < target) {
                i ++;
            }
            else {
                return true;
            }
        }
        
        return false;
    }
}

发表于 2018-09-30 20:45:29 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        for(int i = 0 ;i<array.length;i++){
            int j=array[0].length;
            if(j==0){
                return false;
            }
            if(target<=array[i][j-1]){
                for(int m = 0 ; m<j;m++){
                    if(target==array[i][m]){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

通常情况下,取出每一组的最大值array[i][array[i].length-1]和target进行比较
 如果target小于最大值 那么可以确定 如果存在target的话 则存在改组中,
然后for循环把该组数全部拿出比较 确定则返回true;
另外 进行一次数组无元素的判断;

发表于 2018-09-30 15:52:26 回复(0)
从左到右,依次从上到下遍历进行比较。
   public boolean Find(int target, int [][] array) {
        for (int[] is : array) {
            for (int i : is) {
                if(i == target)
                    return true;
            }
        }
        return false;
    }

发表于 2018-09-30 10:34:29 回复(0)
public class Solution 
{
    public boolean Find(int target, int [][] array) 
    {
        int a1 = array.length;
        int a2 = array[0].length;
        
//        if(target<array[0][0] || target>array[a1-1][a2-1])
//        {
//            return false;
//        }

        for(int i=0;i < a1;i++)
        {
            for(int j=0;j < a2;j++)
            {
                if(array[i][j]==target)
                    return true;
            }
        }
        
        return false;
    }
}

暴力遍历法.请教一下大家,为什么把注释部分加上是错误的.我的思路是先判断target是否在数组的取值区间,然后再遍历

发表于 2018-09-26 10:20:53 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int x = array.length;
        int y = array[0].length;
        if(x == 0 || y == 0) return false;
        for(int i=0;i<x;i++){
            if(array[i][0] == target) return true;
            else if(array[i][0] < target ){
                for(int j=0;j<y;j++){
                    if(array[i][j] == target) return true;
                }
            }
        }
        return false;
    }
}

编辑于 2018-09-20 12:19:40 回复(0)
package ArrayIncre;
import java.util.*;
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)){
            //如果是target<数组中的某个数,则往左边移动
            if(array[len][i]>target){
                len--;
            }else if(array[len][i]<target){
                i++;
            }else{
                return true;
            }         
        }
        return false;
    }
    public static void main(String[] args) {
        //要求从键盘中录入要查找的数
       System.out.println("请输入您要判断的数据:");
       Scanner sc=new Scanner(System.in);
       //获得从键盘中已经录入的数据
       int x=sc.nextInt();
       int array[][]={{1,4,7,9},{2,7,8,11},{4,8,12,19}};
        
        //调用
        Solution s=new Solution();
        boolean result=s.Find(x,array);
        if(result)
            System.out.println("数据含有这样的整数");
        else
            System.out.println("没有这样的整数");
    }
}



在前人的基础上添加了主函数,有不会写主函数的可以可以看看。本人是小白,勿喷。
发表于 2018-09-17 15:21:26 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int lenrow = array.length;
        int lencow = array[0].length;
        int lenrow1 = 0;
        while(lenrow1 < lenrow && lencow>0){
            if(array[lenrow1][lencow-1] < target){
                lenrow1++;
            }else if(array[lenrow1][lencow-1] > target){
                lencow--;
            }else{
                return true;
            }
        }
        return false;
    }
}

发表于 2018-09-04 20:15:41 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int i = 0,j = array[0].length-1;
        while(i<array.length && j>=0){
            if(array[i][j] == target){
                return true;
            }else if(array[i][j] > target){
                j--;
            }else{
                i++;
            }
        }
        return false;
    }
}
发表于 2018-09-03 14:57:08 回复(0)
从矩阵右上角的数开始寻找,比较当前数与要查找的整数,如果当前数与要查找的数相等,直接返回true;如果当前数大于要查找的数,因为每一列数都是从上往下递增的,所以在当前数所在的列中,处于当前数下方的数都大于要查找的数,所以没必要继续在第col列继续查找,令col=col -1;如果当前数小于要查找的数,因为每一行都是从左往右递增的,所以在当前数所在的行中,处于当前数左侧的数都比要查找的数小,因此没有必要在第row行继续查找,令row=row+1;如果发现越界或者没有找到与要查找的数相等的数,直接返回false
发表于 2018-09-03 11:31:32 回复(0)
测试用例:
目标值:5;
二位数组(矩阵):
1 3 5 7 9
2 4 6 8 10
4 6 8 10 12
8 10 12 14
public class Solution {
    public boolean Find(int target, int [][] array) {
        int row = array.length-1;
        int col = 0;//必须从左下角或右上角开始判断,这样才有确定的移动方向,若从某行中间开始则不确定往哪个方向移动;
        //限制坐标,
        while(row>=0 && col<array[row].length){
            //首先必须判断是否命中,否则会得不到准确的boolean值;
            if(array[row][col] == target){
                return true;
            }
            
      //其次判断当前坐标与目标值的大小,小则移动列坐标,大则移动行坐标,注意每移动一次都要利用 continue跳过当前循环,否则同时移动行列坐标可能导致数组下标越界;             if(array[row][col] < target){
                col++; 
                continue;
        }
            if(array[row][col] > target){
                row--;
                continue;
            }
            
        }
            return false;
  
    }
}        

发表于 2018-08-30 13:41:36 回复(0)
二维数组等长且有序,沿对角线比较,类似二分查找

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


发表于 2018-08-29 23:41:35 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
       if(array[0].length == 0)
           return false;
        int l = array[0].length - 1;
        int h = 0;
        while(h <= array[0].length - 1 && l >= 0){
            if(target == array[h][l])
                return true;
            else if(target > array[h][l])
                h++;
            else
                l--;
        }
        return false;
    }
}

发表于 2018-08-27 16:40:54 回复(1)
//直接遍历
public class Solution
{

    public boolean Find(int target, int[][] array)
    {
        boolean flag = false;
        for (int i = 0; i < array.length; i++)
        {
            for (int j = 0; j < array[i].length; j++)
            {
                if (array[i][j] == target)
                {
                    flag = true;
                }
            }
        }


        return flag;
    }
编辑于 2018-08-27 15:33:49 回复(0)
直接贴代码吧,注释很清晰了
import java.util.Scanner;

/*
 * 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,
 * 每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个
 * 整数,判断数组中是否含有该整数
 * */
public class Find {
    public static void main(String[] args) {
        int [][] a={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
        int target;
        Scanner S=new Scanner(System.in); 
        System.out.println("请输入待查找数字:");
        target=S.nextInt();
        boolean consequence=find(a,target);
        System.out.println("这个数字存在:"+consequence);
    }
    public static boolean find(int [][] array,int target){
        int length=array.length-1;//数组长度若为4,则角标最多取到3,
//        这里的length即数组的长度,也即是数组的行数
//        思路:从最左下的一个元素找,如果大于则往右边找,如果小于则往上边找
        int i=0;//i代表第几列
        while((length>=0)&&(i<array[0].length)){
            if(array[length][i]>target){
                length--;
            }else if(array[length][i]<target){
                i++;
            }else{
                return true;
            }
        }
        return false;
    }
}


发表于 2018-08-24 23:10:49 回复(0)
略不成熟思路:
由于二维数组由上至下、由左至右递增:
步骤一:列检索:即检索每行第一个元素a[i][0],若找到则a[i][0] == x,return true;若没有,则记录第一个a[i][0] > x的行号i, 结束列检索,进入步骤二;
步骤二:行检索:在步骤一获得的行号i,由于a[i][0]>x,故该行所有元素均大于x,所以行检索应在i-1行开始,通过二分法,即可得结果!
代码就不列了,嘴泡一下。。。。望采纳!

发表于 2018-08-24 10:12:02 回复(0)
1.二维数组放到容器中;
2.容器中的数据排序,然后依顺序放入数组中;
3.容器二分查找是否有所给数据,有返回true,无false。
发表于 2018-08-18 18:03:28 回复(0)

扫一扫,把题目装进口袋

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

扫描二维码,进入QQ群

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