比左边和上边大的矩阵

昨天遇到一道矩阵的题目。这个矩阵有一个特性,对于任意元素,所有它左边和上边的元素都比它小,或者用形式化的语言来说,任意(x,y),凡是i小于等于x和j小于等于y,且(i,j)不是(x,y),那么(i,j)小于(x,y)。

 1  4  5  8  9
 2  6  7 11 13
 3 10 18 19 20
12 15 21 24 28
14 16 22 25 29

上面给出了一个符合要求的例子,题目问如何查找一个元素是否在矩阵中。

我第一个想法是从左上角开始,先在对角线上找。当要找的值介于两个对角元素之间时,再横着找或竖着找。比如要找7,先是1,往对角线6,然后18,这时6小于7,7小于18,再竖着找。但是其实这种方法是错误的,比如我们要找15,首先也是找到6和18之间,但是之后无论横着找还是竖着找,都找不到15,但15是在矩阵里的。这种方法不行是因为虽然题目说任意元素左边和上边元素比它小,但是并不是比它小的元素都在它左边和上边。

我第二个想法是逐行搜索(或者逐列搜索),因为每一行本身是有序的,所以可以用二分法去搜。这种方法是行得通的,于是我就没有再想下去了。后来请教同学,发现有一种更简单的方法,我估计那就是题目想要的正解。

方法是这样的,从右上角开始。如果元素的值比目标值大,那么说明元素所在的列都比目标值大,所以整列都不用考虑,因此往左移动一格;同样道理,如果元素的值比目标值小,那么元素所在的行都比目标值小,这时应该往下移动一行。这样,算法最坏的复杂度不超过O(m+n),m和n是矩阵的宽度和高度。下面我用C实现了一下。

// val - the value searched
// matrix - the matrix we want to find val
// row - number of rows in matrix
// col - number of columns in matrix
// return 1 if found
// return 0 if not found
int matrixFind(const int val, const int *matrix, const int row, const int col)
{
	int i = 0;
	int j = col - 1;

	while (i < row && j >= 0) {
		int cur = matrix[row * i + j];
		if (cur == val)
			return 1;
		else if (cur > val)
			j--;
		else
			i++;
	}
	return 0;
}

我觉得最后一种解法的巧妙之处在于突破了惯性思维,因为一般情况我们都从左上角想起,但是这个算法从右上角开始,当然,从左下角开始也是可以的。

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s