专栏首页后端CoderLeetCode120|二维数组中的查找

LeetCode120|二维数组中的查找

1,问题简述

在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

2,示例

现有矩阵 matrix 如下:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5,返回 true。

给定 target = 20,返回 false。

 

限制:

0 <= n <= 1000

0 <= m <= 1000
 

3,题解思路

本题基于二维数组给出的特点和hashSet两种思路进行解决,那么接下来看下题解程序是怎么个实现方式吧

4,题解程序

import java.util.HashSet;

public class FindNumberIn2DArrayTest {
    public static void main(String[] args) {
        int[][] matrix = {
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        int target = 5;
        boolean numberIn2DArray = findNumberIn2DArray(matrix, target);
        System.out.println("numberIn2DArray = " + numberIn2DArray);

    }

    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rowLength = matrix.length;
        int colLength = matrix[0].length - 1;
        int row = 0;
        while (row < rowLength && colLength >= 0) {
            if (matrix[row][colLength] == target) {
                return true;
            } else if (matrix[row][colLength] > target) {
                colLength--;
            } else {
                row++;
            }
        }
        return false;
    }

    public static boolean findNumberIn2DArray2(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        HashSet<Integer> hashSet = new HashSet<>(matrix.length * matrix[0].length);
        int rowLength = matrix.length;
        int colLength = matrix[0].length;
        for (int i = 0; i < rowLength; i++) {
            for (int j = 0; j < colLength; j++) {
                if (hashSet.contains(target)) {
                    return true;
                }
                hashSet.add(matrix[i][j]);
            }
        }
        return hashSet.contains(target);
    }
}

5,题解程序图片版

6,总结一下

HashSet集合的使用还是比较常见的,特别是它的contains()方法,使用频率更高,也是我们应该熟知的一些内容,特别是对于应用的开发人员

本文分享自微信公众号 - WwpwW(gh_245290c1861a),作者:后端Coder

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode11|搜索二维矩阵

    编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

    码农王同学
  • LeetCode53|搜索二维矩阵II

    编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:

    码农王同学
  • LeetCode83|排序矩阵查找

    写这道题时,自己还是有点想快点写的感觉,总是想着赶紧写完,但是过犹不及,还是老老实实写吧,这样自己的内心还是比较平静,毕竟我们没有必要以体量或者方法来说一个人优...

    码农王同学
  • LeetCode11|搜索二维矩阵

    编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

    码农王同学
  • LeetCode53|搜索二维矩阵II

    编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:

    码农王同学
  • 搜索二维矩阵Ⅱ

    一份执着✘
  • (力扣)面试题04. 二维数组中的查找

    [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13,...

    TrueDei
  • leetcode417. Pacific Atlantic Water Flow

    假设左上角的所有周围面积为太平洋,右下角的所有面积为大西洋。现在使用数组来表示一大片水域,其中数组的每一个位置上的元素代表某一个小水域的高度。假定水只能从高出流...

    眯眯眼的猫头鹰
  • LeetCode(面试题:二维数组中的查找)

    TrueDei
  • LeetCode刷题记录:剑指 Offer 04. 二维数组中的查找

    在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断...

    英雄爱吃土豆片

扫码关注云+社区

领取腾讯云代金券