《剑指Offer》Java刷题 NO.1二维数组的查找

《剑指Offer》Java刷题 NO.1二维数组的查找(数组、二分法)

时间：2020-02-02 基础不是很扎实，虽然这题比较简单但是也用了不少时间

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

Java代码：

public class TwoDimensionArraysSearch {
          
   
    /**
     *第一种方法：二分查找
     * 时间复杂度：O(NlogN)
     * 运行时间：202ms;占用内存：16928k
     */
    public boolean binaryFind(int target,int [][]array){
          
   

        if(array==null||array.length==0) return false;//判定数组空
        //变量定义
        int left,right,mid;

        //遍历每一行
        for(int i=0;i<array.length;i++){
          
   

            if(array[i]==null||array[i].length==0) return false;//判定数组空

            //变量初始化
            left=0;
            right=array[i].length-1;

            while(left<=right){
          
   
            //如果待查询的范围最后只剩两个数，那么position 一定会指向
            //下标靠前的数字，因为(n+(n+1))/2=n;
                mid=(left+right)/2;

                if(array[i][mid]>target)
                    right=mid-1;//可以-1，也可以不写，-1效率更高

                else if(array[i][mid]<target)
                    left=mid+1;//必须+1，否则找最后一个数时陷入死循环

                else return true;
            }
        }
        return false;
    }

    /**
     * 最优解
     * 思路：从最大行第一列开始查询，若比目标大则行减一，若比目标小则列加一
     * 时间复杂度：O(N)(假设列数为N)
     * 运行时间：193ms； 占用内存：18412k
     */
    public boolean find(int target,int [][]array){
          
   

        if(array==null||array.length==0) return false;//判定数组空

        //变量定义及初始化
        int row=array.length-1;
        int col=0;

        while(row>=0&&col<array[0].length){
          
   //行列均未出界
            if(array[row][col]>target)
                row--;
            else if(array[row][col]<target)
                col++;
            else return true;
        }
        return false;
    }
    public static void main(String args[]){
          
   
        int[][] arrays={
          
   {
          
   1,2,8,9},{
          
   2,4,9,12},{
          
   4,7,10,13},{
          
   6,8,11,15}};
        TwoDimensionArraysSearch findNum=new TwoDimensionArraysSearch();
        boolean result=findNum.find(16,arrays);
        System.out.println(result);

    }
}

C++:

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

/*最优解思路同上
运行时间：16ms
占用内存：1400k*/

using namespace std;
class Solution {
          
   
public:
    bool Find(int target, vector<vector<int> > array) {
          
   
        if (array.empty()) return false;
        int row = array.size()-1;
        int col = 0;
        while ((row >= 0) && (col < array[0].size())) {
          
   
            if (target > array[row][col]) col++;
            else if (target < array[row][col]) row--;
            else return true;
        }
        return false;
    }
};

int main()
{
          
   
    Solution so;
    vector<vector<int> > array;
    array = {
          
    {
          
   1, 2, 8, 9} ,{
          
   2, 4, 9, 12},{
          
   4, 7, 10, 13},{
          
   6, 8, 11, 15} };
    cout << so.Find(7, array) << endl;
}