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---二维数组中的查找

1、介绍

2、题解