【题4二维数组中的查找】Java实现

太过爱你忘了你带给我的痛 2022-04-10 10:19 137阅读 0赞

**【题4二维数组中的查找】**  
**【题目】**  
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数  
**【方法】**  
选取数组中右上角的数组若等于查找数字，则完成  
若大于查找数字，则剔除所在列  
若小于查找数字，则剔除所在行  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]

**实现**

package ti4;
    
    //二维数组中查找
    public class Main{
        public boolean Find(int target, int [][] array) {
            if(array.length==0 || array[0].length==0)
                return false;
            int m = array[0].length-1;
            int n = 0;
            int temp = array[n][m];
            while(target != temp){
                if(m>0 && n<array.length-1){
                    if(target>temp){
                        n = n + 1;
                    }else if(target<temp){
                        m = m - 1;
                    }
                    temp = array[n][m];
                }else{
                    return false;
                }
            }
            return true;
        }
    }

测试代码：

package ti4;
    
    import java.util.Scanner;
    import ti4.Main;
    
    public class TestMain {
    	public static void main(String[] args) {
    		Main m1 = new Main();
            int[][] arr = {
                {1,2,8,9},
                {2,4,9,12},
                {4,7,10,13},
                {6,8,11,15},
                {8,10,14,17}
            };
            System.out.println(m1.Find(8, arr));//true
            System.out.println(m1.Find(22, arr));//false
        }
    }

参考：  
1.《剑指offer》  
2.[https://www.2cto.com/kf/201506/407300.html][https_www.2cto.com_kf_201506_407300.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220331/be281499ee8c44deb96b55c6e1dfd461.png
[https_www.2cto.com_kf_201506_407300.html]: https://www.2cto.com/kf/201506/407300.html