leetcode-二维数组中的查找-49-白红宇的个人博客

leetcode-二维数组中的查找-49

发布日期：2021-05-08 20:30:29 浏览次数：14 分类：精选文章

本文共 1041 字，大约阅读时间需要 3 分钟。

题目要求

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

思路

方法一，蛮力法，将target在二维数组中一个一个去比较，如果有就返回true，没有就是false。

方法二，利用类似二叉树的结构，将二维数组右上角的那个数据看成root结点，左边的数据是他的左子树，下边的数据是他的右子数，然后通过对比target和当前结点的值，如果target大，行加1，如果小，列减一，进行查找。

代码实现

方法一

class Solution {public:	bool findNumberIn2DArray(vector
   
    
     >& matrix, int target) {		//蛮力法		if (matrix.size() == 0 || matrix[0].size() == 0)		{			return false;		}		int rows = matrix.size(), columns = matrix[0].size();		for (int i = 0; i < rows; i++)		{			for (int j = 0; j < columns; j++)			{				if (matrix[i][j] == target)				{					return true;				}			}		}		return false;	}};

方法二

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

上一篇：Linux-线程终止-线程等待-线程分离-线程安全

下一篇：leetcode-数组中重复的数字-48

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章