剑指Offer:面试题04. 二维数组中的查找
本文最后更新于 1727 天前,其中的信息可能已经有所发展或是发生改变。

面试题04. 二维数组中的查找

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

示例:

现有矩阵 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

要点

  • 剪枝
  • 二分查找

二分查找注意边界条件,可以看看大佬的文章

代码

image

感觉这玩意有问题

public boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            if(matrix[i].length-1<0||matrix[i][0]>target||matrix[i][matrix[i].length-1]<target){
                continue;   
            }
            int low=0;
            int heigh=matrix[0].length-1;
            while(low<=heigh){
                int mid=low+((heigh-low)>>1);
                if(matrix[i][mid]>target){
                    heigh=mid-1;
                }else if(matrix[i][mid]<target){
                    low=mid+1;
                }else{
                    return true;
                }
            }
        }
        return false;
    }
作者:Yuyy
博客:https://yuyy.info
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇