[剑指Offer]二维数组中的查找(CC++描述)

题目描述

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

  • 思路一
  1. 让target与数组最右上角(左下角类似)比较,若相等则返回true
  2. 若target nums[top][right],则说明应该在该行下方找,故top++
  3. 若target  nums[top][right],则说明应该在该行左方找,故right--
  • 思路二
  1. 对每一行进行二分查找,找到则返回,找不到,找下一行,直到行结束
C语言描述
bool searchMatrix(int** matrix, int matrixRowSize, int matrixColSize, int target) 
{
    if(matrix == NULL || matrixColSize == NULL || matrixRowSize == 0)
    	return false;
    int right = matrixColSize-1, top = 0;
    while(top  matrixRowSize  right = 0)
    {
    	if(matrix[top][right] == target)
    		return true;
    	else if(matrix[top][right]  target)
    	{
    		top++;
    	}
    	else if(matrix[top][right]  target)
    	{
    		right--;
    	}
    }
    return false;
}
C++描述 
class Solution 
{
public:
    bool Find(int target, vectorvectorint  array) 
    {
        if( array.size()==0 )
            return false;
        if( array[0].size()==0)
            return false;
        int right = array[0].size()-1, top = 0;
        while(top  array.size()  right = 0)
        {
            if(array[top][right] == target)
                return true;
            else if(array[top][right]  target)
            {
                top++;
            }
            else if(array[top][right]  target)
            {
                right--;
            }
        }
        return false;
    }
};

 

最新回复(0)
/jishuB8eJIvZirXXFe_2Flv3FBjpl9q8RyVZHWNrpCsyw_3D_3D4795357
8 简首页