剑指Offer-面试题4---二维数组中的查找

1、介绍

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

2、题解

1.我的写法：
每次比较二维数组一行的最后一个数。如果最后一个数>=目标数，则在这行中倒着比较；如果最后一个数<目标数，则到下一行中继续这个过程。
C++实现

bool Find1(vector< vector<int> > arr,int target)
{
    //获取宽和列
    int row = arr.size();
    int col = arr[0].size();
    //参数有误则直接返回
    if(row == 0 || col == 0) return false;
    if(arr[0][0]>target || arr[row-1][col-1]<target) return false;

    for(int i=0;i<row;i++){
        if(arr[i][col-1] >= target){
            for(int j=col-1;j>=0;j--){
                if(arr[i][j] == target){
                    return true;
                }
                else if(arr[i][j] < target){
                    break;
                }
            }
        }
    }
    return false;
}

2.更好的写法：
从二维数组右上角开始比较。如果小于目标数则行数++；如果大于目标数则列数--。
时间复杂度：O(行高 + 列宽)
C++实现

bool Find2(vector< vector<int> > arr,int target)
{
    int row = arr.size();
    int col = arr[0].size();
    if(row == 0 || col == 0) return false;
    if(arr[0][0]>target || arr[row-1][col-1]<target) return false;

    int i=0;
    int j = col-1;
    while(i<row && j>=0){
        if(arr[i][j] < target){
            i++;
        }
        else if(arr[i][j] > target){
            j--;
        }
        else{
            return true;
        }
    }
    return false;
}

Lua实现

myArray = {}

for i=1,2,1 do
    myArray[i] = {}
end
--自定义的一个二维数组(2行3列)
local temp = 1
for i=1,2,1 do
    for j=1,3,1 do
        myArray[i][j] = temp
        temp = temp + 1
    end
end

function SearchNumber(arr,targetNum)
    local row = #arr
    local column = #arr[1]

    local i = 1
    local j = column

    --从右上角开始比较
    while(i<=row and j>=1) do
        if(arr[i][j] > targetNum) then
            j = j-1
        elseif(arr[i][j] < targetNum) then
            i = i+1
        else
            return true
        end
    end
    return false
end

local isFind = SearchNumber(myArray,7)

if find==nil then
    print('未找到目标数字')
else
    print('找到目标数字')
end

剑指Offer---面试题4---二维数组中的查找

原文：https://www.cnblogs.com/Fflyqaq/p/11890641.html