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

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 回复(218)
/**
*解题大概思路 :清楚二维数组是从上到下,从左到右有序,从左下角开始比较,假如比较元素大于左下角,列向右移动(++),假如比较元素小于左上角行向上移动(--),依此类推不断的进行比较
*
*/
public boolean Find(int target, int [][] array) {
        int rows = array.length-1;    //行数
        if(rows == 0){    //边界判断
            return false;
        }
        int currentcolumns = 0;//array[0].length;
        int columns = array[0].length;    //列数
        //从左下比较
        while(rows>=0 && currentcolumns < columns){
            if(target < array[rows][currentcolumns]){//行减1
                rows--;
            }else if(target > array[rows][currentcolumns]){ //列加1
                currentcolumns++;
            }else{
                return true;
            }
        }
        
        return false;
    }
}

发表于 2019-11-06 11:24:27 回复(0)
public boolean Find(int target, int [][] array) {
        int xmax;
        int ymax;
        if (array.length == 0 || array == null) {
            return false;
        }
        System.out.println(1111);
        for (int a = 0; a < array.length; a++) {
            xmax = array[a][array.length - 1];
            ymax = array[array.length - 1][a];
            System.out.println("x: " + xmax + " y: " + ymax);
            if (target <= xmax) {
                for (int b = 0; b < array.length; b++) {
                    if (target == array[a][b]) {
                        return true;
                    }
                }
            }
            if (target <= ymax) {
                for (int b = 0; b < array.length; b++) {
                    if (target == array[b][a]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

用例:
16,[[]]

对应输出应该为:

false

你的输出为:

java.lang.ArrayIndexOutOfBoundsException: 0
还这样 为什么?
发表于 2019-11-05 16:53:20 回复(0)

注意点:

  1. 判断数组是否为空。

            // 因为数组的每行长度相同,先求出每行长度,行数
            int row = array.length;
            int column = array[0].length;
    
            // 先判空
            if (row == 0 || column == 0) {
                return false;
            }
  2. 因为二维数组有序,先判断目标是否在范围内:a[0][0]~~a[row][column],不在直接返回false。

  3. 用双重循环遍历时, 先和该行最后一个比较(因为在该行这个数最大),如果target大于这个数,直接结束该层(内层)循环,减少遍历次数。

发表于 2019-10-27 15:13:56 回复(0)
import java.util.Arrays;

public class Solution {
    public boolean Find(int target, int [][] array) {
        boolean flag = false;
        for(int[] arrs : array) {
            flag = Arrays.stream(arrs).filter((num) -> num == target).count() != 0;
            if (flag) {
                return true;
            }
        }
        return flag;
    }
}

发表于 2019-10-18 17:00:47 回复(0)
 public boolean Find(int target, int [][] array) {
        int row = array.length-1;
        int col = array[0].length-1;
 
        for(int i = col; i >= 0; --i){
            if(array[0][i] > target)
                col--;
            else
                break;
        }
        if(col == -1) return false;
 
        for(int i = row; i >= 0; --i){
            if(array[i][0] > target)
                row--;
            else
                break;
        }
        if(row == -1) return false;
 
        while(row >= 0 && col >= 0){
            if(array[row][col] == target) return true;
            else if(array[row][col] > target){
                for(int i = 0; i < row; ++i){
                    if(array[i][col] == target)
                        return true;
                }
                for(int i = 0; i < col; ++i){
                    if(array[row][i] == target)
                        return true;
                }
                row--;
                col--;
            }
            else
                return false;
        }
        return true;
    }

就运行时间来说,比左下角开始找快,分别遍历最左边一列和最上边一行,将索引范围缩小。
从新的矩阵的右下角开始向左上找,如果找到target返回true,如果比target大,那就遍历当前行和列,如果比target小,说明target不在该点和(0,0)构成的矩阵中,而该矩阵以外的范围也都已经扫描过了,所以没有这个数。
发表于 2019-10-16 23:51:44 回复(0)
/**  * 功能描述: ①数组第一题  * 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从  * 上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数  * 1    2   3   4   5   6  * 7    8   9  10  11  12  *  * 考点: 二分查找的非递归方式  */
public boolean Find(int target, int[][] array) {
        for (int i = 0; i < array.length; i++) {
            int low = 0;
            int high = array[i].length - 1;
            int mid;
            while (low <= high) {
                mid = (low + high) / 2;
                if (array[i][mid] == target) {
                    return true;
                } else if (array[i][mid] < target) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return false;
    }



发表于 2019-10-03 16:36:41 回复(0)

二维数组

数组的数组---二维数组的每一个元素是一个一维数组

定义格式

数据类型[][] 数组名 = new 数据类型[二维数组的长度/包含的一维数组的个数][每个一维数组的长度];

int[][] arr = new int[3][5];---定义了一个整型的二维数组,其中包含3个一维数组,每个一维数组可以存储5个整数

arr[0]---下标为0的位置上的一维数组

arr[1][3]---如果要获取具体的元素需要两个下标
//arry.length的值为一维数组的个数
//arry[i].length 为第i个一维数组的长度

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(array[i][j]==target)
                    return true;
            }
        }
        return false;
    }
}


发表于 2019-09-22 10:29:37 回复(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) {
            if (array[row][col] > target) {
                row--;
            } else if (array[row][col] < target) {
                col++;
            } else {
                return true;
            }
        }
        return false;
    }
}
发表于 2019-09-12 13:54:36 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array == null) {
            return false;
        }
        int rows = array.length;
        if(rows == 0) {
            return false;
        }
        int cols = array[0].length;
        if(cols == 0) {
            return false;
        }
        int i = rows - 1;
        int j = 0;
        while(true) {
            if(target > array[i][j]) {
                if(j == cols - 1) {
                    return false;
                }
                j++;
            }else if(target < array[i][j]) {
                if(i == 0) {
                    return false;
                }
                i--;
            }else {
                return true;
            }
        }
        
    }
}

发表于 2019-09-08 20:29:58 回复(1)
public class Solution {
    public boolean Find(int target, int [][] array) {
       for(int[] arr : array){
           for(int i =arr.length-1;i>=0;i--){
               if(arr[i]<target){
               break;
               }
               else{
                if(arr[i]==target)
                 return true;
               }
           }
       }
        return false;
    }
}
从数组的右上角开始查,如果target大则往下移,小则往左移动
发表于 2019-09-06 19:22:55 回复(0)
虽然知道自己很菜,但是还是贴一下自己的代码,使用的是java语言
public class Solution {
    public boolean Find(int target, int [][] array) {
        int MAX_i = array.length-1;
        int MAX_j = array[0].length-1;
        if(MAX_i==0 || MAX_j==0){
            return false;
        }
        for(int i=0;i<=MAX_i;i++){
            if(target<array[i][0]){
                return false;
            }else{
                if(target==array[i][MAX_j]){
                    return true;
                }else if(target>array[i][MAX_j]){
                    //target不在此行,开始下一轮i循环
                }else{//target可能在此行,使用j循环检查
                    for(int j=0;j<MAX_j;j++){
                        if(target==array[i][j]){
                            return true;
                        }else{
                            //开始下一轮j循环
                        }
                    }
                }
            }
        }
        return false;
    }
}

发表于 2019-09-05 20:29:34 回复(0)
    /**
     * 暴力遍历
     * @param target
     * @param array
     * @return
     */
    public static 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][j]){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 从左下角开始比较,target大与当前值则右移,小于当前值则上移
     */
    public static boolean fint2(int target, int[][] array) {
        if(array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }

        // 行数
        int rowIndex = array.length - 1;
        // 列数
        int i = 0;

        while(i<=array[0].length - 1 && rowIndex >= 0){
            if(target == array[rowIndex][i]) {
                return true;
            } else if(target > array[rowIndex][i]) {
                ++i;
            } else {
                --rowIndex;
            }
        }
        return false;
    }


编辑于 2019-09-04 09:56:27 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        if (array.length == 0 || array[0].length == 0) return false;
        int j = array.length-1;
        int i =0;
        if (array[j][0] == target) return true;
        for(int n=0;n<array[0].length+j;n++){
            if (array[j][i] > target) j--;
            else i++;
            if(i >= array[0].length) return false;
            if(j < 0) return false;
            if(array[j][i] == target) return true;
        }
        return false;
    }
}
发表于 2019-09-03 11:24:30 回复(0)
首先别进入误区:二维数组输入的可以是有序的而不是随机输入数组然后调整数组内部结构使之有序(会复杂很多)!!!java数组没有多维性,都统一看做一维数组!!!第一个下标都是代表有多少个一维数组!!!
1.变化关系:观察可以发现从左下角的数,向上走是减小,向左走是增大,而行列数,向上走是行减小,向右走是列增大。(也可以发现其他关系)
2.利用变化关系写出相关算法
发表于 2019-09-02 09:35:39 回复(0)
考察的是查找算法,使用了比较熟的二分查找suanfa
发表于 2019-08-29 14:10:15 回复(0)

1最暴力破解
直接建立两个循环进行匹配
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array == null){
            return false;
        }
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[0].length;j++){
                if(target==array[i][j]){
                    return true;
                }
            }
        }
        return false;
    }
}
时间复杂度:O(n^2)
空间复杂度:O(1)
问题
  • 时间复杂度太高了,属于暴力破解
  • 根本没有用到矩阵有序的这一点
2二维数组的二分查找
把每一行看成有序递增的数组,利用二分查找,通过遍历每一行得到答案,
由矩阵的的递增性我们可以将target>array[i][mid]时,mid之后的不予考虑,虽然时间复杂度不会减少,但是理论上时间会减少一些
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array == null){
            return false;
        }
        int r = array.length;
        int c = array[0].length;
        for(int i=0;i<r;i++){
            int low = 0;
            int high = c - 1;
            while(low <= high){
                int mid = (low+high)/2;
                if(target == array[i][mid]){
                    return true;
                }else if(target>array[i][mid]){
                    low = mid + 1;
                }else if(target<array[i][mid]){
                    high = mid - 1;
                    c = mid;
                }
            }
        }
        return false;
    }
}
时间复杂度:O(nlogn)
空间复杂度:O(1)
3
矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,因此从左下角开始查找,目标比左下角数字大时。右移;目标比左下角数字小时,上移;当然也可以从右上角进行查找,目标比右上角小时,下移;目标对右上角大时,左移;
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array == null){
            return false;
        }
        int r = array.length-1;
        int c = array[0].length;
        int i,j;
        for(i=r,j=0;i>=0&&j<c;){
            if(target == array[i][j]){
                return true;
            }else if(target > array[i][j]){
                j++;
            }else if(target < array[i][j]){
                i--;
            }
        }
        return false;
    }
}
时间复杂度:O(n)
空间复杂度:O(1)

以上思路部分是参考了牛客大神的,我这里做了一下自我的总结和编写,给大家参考



发表于 2019-08-27 10:14:38 回复(0)
解题思路:题目说矩阵是有序的,那么可以从左下角开始和 target 比较,如果比 target 小就往右位移,如果比 target 大就往上位移,直至越界或者找到目标。
public class Solution {
    public static boolean Find(int target, int [][] array) {
        if(array.length<0)
            return false;
        int i = array.length-1,j=0;
        boolean flag = false;
        while(!flag && i>=0 && j<array[0].length){
            if(array[i][j]>target) --i;
            else if(array[i][j]<target) ++j;
            else flag = true;
        }
        return flag;
    }
}


发表于 2019-08-26 19:23:47 回复(0)
我的思路比较简单,为了满足题目的要求的二维数组,直接把二维降维成1维的,然后从小到大排序,然后还原成二维数组判断就简单多了,比较傻的办法😂😂
发表于 2019-08-23 19:00:58 回复(0)
各位大佬,我这个编译只是else if和if的区别,为什么就不能通过编译呢???求各位大佬解答啊
发表于 2019-08-20 10:47:27 回复(2)
从数组的右上角开始查找,如果对应的数组元素大于该整数则舍弃整列,否则如果对应的数组元素小于该整数则舍弃整行,否则等于则输出true.
public class Solution {
    public boolean Find(int target, int [][] array) {
        int row = array.length;
        int column = array[0].length;
        boolean result = false;
        if(row>0 && column>0){
            int r=0, c=column-1;//从右上角开始查找。
            while(r<row && c>=0){
                if(array[r][c]==target){
                    result = true;
                    break;
                }
                else if(array[r][c]>target)
                    c -= 1;
                else 
                    r += 1;
            }
        }
        return result;
    }
}


发表于 2019-08-18 16:56:27 回复(0)