首页 > 试题广场 >

二维数组中的查找

[编程题]二维数组中的查找
  • 热度指数：2367261 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 ， 矩阵中的值满足
进阶：空间复杂度 ，时间复杂度
示例1

输入

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

true

说明

存在7，返回true
示例2

输入

1,[[2]]

输出

false
示例3

输入

3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

false

说明

不存在3，返回false
算法知识视频讲解
添加回答
推荐
徘徊的路人甲头像 徘徊的路人甲 
/* 思路
* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时，上移
*/

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 回复(249)
Java
牛客707198064号头像 牛客707198064号
按照双方向二分查找，这个思路有什么问题吗？有个测试用例通不过，请大神下
发表于 2023-12-15 16:59:21 回复(0)
Java
Lengxf_头像 Lengxf_ 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param target int整型
     * @param array int整型二维数组
     * @return bool布尔型
     */
    public boolean Find (int target, int[][] array) {
        // write code here
        if (array == null || array.length == 0) {
            return false;
        }
        int x = 0;
        int y = array.length - 1;
        while (x < array[0].length && y >= 0) {
            if (array[y][x] > target) {
                y--;
            } else if (array[y][x] < target) {
                x++;
            } else {
                return true;
            }
        }
        return false;
    }

}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param target int整型
     * @param array int整型二维数组
     * @return bool布尔型
     */
    public boolean Find (int target, int[][] array) {
        // write code here
        if (array == null || array.length == 0) {
            return false;
        }
        int x = 0;
        int y = array.length - 1;
        while (x < array[0].length && y >= 0) {
            if (array[y][x] > target) {
                y--;
            } else if (array[y][x] < target) {
                x++;
            } else {
                return true;
            }
        }
        return false;
    }

}

编辑于 2023-12-06 15:20:37 回复(0)
Java
牛客169782643号头像 牛客169782643号 
//矩阵有序的思路 y轴代表二维数组第一个  x轴代表第二个
public boolean Find (int target, int[][] array) {
        // write code here
        int y = array.length - 1; 
        int x = 0;
        while (y >= 0 && x < array[0].length) {
            if (array[y][x] > target) {
                y --;
            } else if (array[y][x] < target) {
                x ++;
            } else {
                return true;
            }
        }
        return false;
    }

发表于 2023-10-12 11:21:21 回复(0)
Java
长久缄默静待雷声头像 长久缄默静待雷声
我有一个想法就是：按照列进行数组的二分，每次二分以后都重复进行对分好的数组的左上角右下角组成区间，用目标值进行判断，在区间内继续划分，不在就返回抛弃该区间去往另一半区间继续这个过程，直到划分到只有一列时，进行区间判断后满足条件，直接对该列进行二分查找，
 
package cn.sycoder.domain;

public class TwoFenSearch {

    // 主函数，用于判断是否存在目标值
    public static boolean searchInMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        // 如果目标值小于左上角或大于右下角，直接返回 false
        if (target < matrix[0][0] || target > matrix[rows - 1][cols - 1]) {
            return false;
        }

        // 调用递归搜索函数，初始搜索区域为整个矩阵
        return searchInSubMatrix(matrix, target, 0, 0, rows - 1, cols - 1);
    }

    // 递归搜索函数，在指定区域内搜索目标值
    public static boolean searchInSubMatrix(int[][] matrix, int target, int rowStart, int colStart, int rowEnd, int colEnd) {
        // 如果搜索区域为空，直接返回 false
        if (rowStart > rowEnd || colStart > colEnd) {
            return false;
        }

        int topLeft = matrix[rowStart][colStart];
        int bottomRight = matrix[rowEnd][colEnd];

        // 如果目标值在当前区域的范围之外，返回 false
        if (target < topLeft || target > bottomRight) {
            return false;
        }

        // 如果目标值等于左上角或右下角，返回 true
        if (target == topLeft || target == bottomRight) {
            return true;
        }

        // 在当前列进行二分查找，找到下一个可能的搜索起点
        int colMid = (colStart + colEnd) / 2;
        int rowMid = rowStart;
        while (rowMid <= rowEnd && matrix[rowMid][colMid] <= target) {
            if (matrix[rowMid][colMid] == target) {
                return true;
            }
            rowMid++;
        }

        // 在左上和右下两个子区域继续递归搜索
        return searchInSubMatrix(matrix, target, rowMid, colStart, rowEnd, colMid - 1) ||
                searchInSubMatrix(matrix, target, rowStart, colMid + 1, rowMid - 1, colEnd);
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {1, 3, 5, 7},
                {2, 4, 6, 8},
                {3, 6, 9, 12},
                {10, 13, 14, 16}
        };

        int target = 7;
        System.out.println(searchInMatrix(matrix, target));  // 输出: true
    }
}


发表于 2023-08-23 15:58:13 回复(0)
Java
牛客533503588号头像 牛客533503588号 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param target int整型
     * @param array int整型二维数组
     * @return bool布尔型
     */
    public boolean Find (int target, int[][] array) {
        // write code here
        for (int[] intArr : array) {
            if (intArr.length > 0 && intArr[0] <= target) {
                if (Arrays.binarySearch(intArr, target) >= 0) {
                    return true;
                }
            } else {
                break;
            }
        }
        return false;
    }
}

发表于 2023-08-10 22:26:50 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public boolean Find (int target, int[][] array) {
        // 左下元素，大于上方元素，小于右方元素
        //由左下角元素为起点，目标元素大就往右，目标元素小就往上
        //到了边界以后没找到该元素，那就是不存在return false
        if(array.length==0||array[0].length==0) return false;
        int i=array.length-1;
        int j=0;
        while(i>=0&&j<=array[0].length-1){
            if(target>array[i][j]){
                j++;
            }else if(target<array[i][j]){
                i--;
            }else{
                return true;
            }
        }
        return false;
      
    }

发表于 2023-07-31 12:13:08 回复(0)
Java
牛客483756000号头像 牛客483756000号
我用的是二分查找，因为刚写了普通数组的二分查找，这个二维数组，也就是多了几行的数组，那么只需要遍历一下每行的数组出来，走二分查找就好了。
发表于 2023-07-31 09:51:26 回复(0)
Java
ryougishiky头像 ryougishiky 

public boolean Find (int target, int[][] array) {
        if (array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }
        int rows = array.length, cols = array[0].length;
        int r = 0, c = cols - 1; // 从右上角开始
        while (r <= rows - 1 && c >= 0) {
            if (target == array[r][c]) {
                return true;
            } else if (target > array[r][c]) {
                r++; // 当前值比目标值小，排除这一行
            } else {
                c--; // 当前值比目标值大，排除这一列
            }
        }
        return false; // 没有找到
    }

发表于 2023-07-24 16:22:10 回复(0)
Java
Brightme头像 Brightme
在行数不为0的情况下，要判断二维数组是否为空只能遍历每行，若每行长度都为0，二维数组才为空。 
if(array.length == 0 )
            return false;
        boolean isEmpty = true;
        for(int j = 0;j < array.length;j++)
        {
            if(array[j].length != 0)
            {
                isEmpty = false;
                break;
            }    
        }
        if(isEmpty)
            return false;

发表于 2023-07-02 18:14:32 回复(0)
Java
加麻加辣的菜鸡很emo头像 加麻加辣的菜鸡很emo
二分查找： 
import java.util.*;
public class Solution {
    public boolean Find(int target, int [][] array) {
        int n = array.length;
        int m = array[0].length;
        if (m == 0) return false;
        //先搜索第一行
        int left = 0, right = m-1;
        if (array[0][0] > target) return false;
        while (left < right) {
            if (array[0][right] > target) right--;
            else break;
        }
        while (left <= right) {
            if (array[n-1][left] < target) left++;
            else break;
        }
        List<Integer> search = new ArrayList<>();
        for (int i=left; i<=right; i++) {
            search.add(i);//添加所有需要搜索的列
        }
        for (int j=0; j<search.size(); j++) {
            left = 0;
            right = n-1;
            if (array[left][search.get(j)] == target) return true;
            if (array[right][search.get(j)] == target) return true;
            while (left <= right) {
                int mid = (left + right)/2;
                if (array[mid][search.get(j)] < target) left = mid + 1;
                else if (array[mid][search.get(j)] > target) right = mid - 1;
                else return true;
            }
            if (array[left][search.get(j)] == target) return true;
            if (array[right][search.get(j)] == target) return true;
        }
        return false;
    }
}


发表于 2023-06-10 09:54:54 回复(0)
Java
我是小韩头像 我是小韩

啥也不说了，双层for循环，妥妥的

public class Solution {
    public static boolean Find(int target, int [][] array) {
        if (array.length == 0 || array[0].length == 0) {
            return false;
        }
        for (int row = 0; row < array.length; row++) {
            if (array[row][0] > target) {
                break;
            }
            for (int i = 0; i < array[row].length; i++) {
                if (array[row][i] > target) {
                    break;
                }
                if (array[row][i] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}
发表于 2023-05-16 08:02:22 回复(0)
Java
糊涂的西红柿蚌埠住了头像 糊涂的西红柿蚌埠住了
public boolean Find(int target, int [][] array) {      
        int n = array[0].length;
        int m = array.length;
        if(m==0||n==0)return false;
        for (int i = m - 1, j = 0; i >= 0 && j < n;) {
            if (array[i][j] > target)
                i--;
            else if (array[i][j] < target)
                j++;
            else return true;
        }
        return false;
    }
发表于 2023-05-02 17:04:24 回复(0)
Java
Neo_Trinity头像 Neo_Trinity 
public class Solution {
    public boolean Find(int target, int [][] array) {
        for (int idx = 0; idx < array[0].length; idx++) {
            boolean flag = binSearch(target, array[idx], 0, array[idx].length - 1);
            if (flag) {
                return true;
            }
        }
        return false;
    }

    public boolean binSearch(int target, int[] arr, int start, int end) {
        if (start < 0 || end < 0 || start >= arr.length || end >= arr.length) {
            return false;
        }
        if ((end - start) < 0) {
            return false;
        } else if ((end - start) <= 1) {
            return target == arr[start] || target == arr[end];
        } else {
            boolean flag = false;
            int middle = (end - start) / 2;
            if (target <= arr[middle]) {
                flag = binSearch(target, arr, start, middle);
            } else {
                flag = binSearch(target, arr, middle + 1, end);
            }
            return flag;
        }
    }
}

二分查找靠谱点，二维数组虽然满足 按行 按列递增，
但是并没说元素不可重复，不同行的 数据范围可能重叠。
发表于 2023-04-27 10:12:32 回复(0)
Java
十四加油头像 十四加油
public class Solution {
public boolean Find(int target, int [][] array) {
int left = 0;
int right = 0;
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;
}
}

发表于 2023-04-16 00:19:56 回复(1)
提交观点

问题信息

数组
来自：2015年度信息化技能...
难度：
600条回答 1520977浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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