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

题目

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

答案

#include <iostream>
#include <vector>

bool FindInPartiallySortedMatrix(std::vector<std::vector<int>>, int);

int main(int argc, char* argv[])
{
	std::vector<std::vector<int>> matrix = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} };
	bool rst = FindInPartiallySortedMatrix(matrix, 2);
	return 0;
}

bool FindInPartiallySortedMatrix(std::vector<std::vector<int>> matrix, int target)
{
	if (matrix.size() == 0)
		return false;
	size_t col = matrix[0].size();
	for (auto& iter : matrix)
	{
		if (iter.size() != col) // in case of each row in matrix doesn't have the same length
			return false;
	}
	int row = matrix.size();
	int rowIdx = row - 1, colIdx = 0;
	while (rowIdx >= 0 && colIdx <= col - 1)
	{
		if (matrix[rowIdx][colIdx] == target)
			return true;
		else if (matrix[rowIdx][colIdx] > target)
			--rowIdx;
		else
			++colIdx;
	}
	return false;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

5 × 5 =

45 + = 46