• 00001.二维数组中的查找
  • 发布于 1个月前
  • 35 热度
    0 评论

题目描述:


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



解题思路:

1. 对于无序的或者不规律的二维数组,只能采取暴力解决,例如:




public class Solution {
    public boolean Find(int target, int [][] array) {
        //无脑暴力
        for(int row = 0; row < array.length; row++) {
            for(int col = 0; col < array[0].length; col++) {
                //关键对比
                if(array[row][col] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

解题思路:

2.抓取主干信息,每行元素和每列元素都是有规律,暴力的复杂度为O(n^2),优化思路就在这个规律上。暴力慢就慢在无法判断每次移动的方向,所以只能按照每行递增然后再每列递增的固定套路去一个一个的尝试。而题目加粗部分,则表达出我可以选定固定位置,然后每次只移动一步,要么向上要么向下,确定了每次的方向,所以复杂度为O(n)。

public class Solution {
    public boolean Find(int target, int [][] array) {
        //声明行长度和列长度
        int rowCount = array.length;
        int colCount = array[0].length;
        //确定起始位置为左下脚。当然也可以是任意的四个角
        int row =  rowCount - 1;
        int col = 0;
        //循环条件在于判断
        while(row > -1 && col < colCount) {
            if(target == array[row][col]) {
                return true;
            } else if(target < array[row][col]){
                --row;
                continue;
            } else {
                ++col;
                continue;
            }
        }
        return false;
    }
}


用户评论