比左边和上边大的矩阵

昨天遇到一道矩阵的题目。这个矩阵有一个特性,对于任意元素,所有它左边和上边的元素都比它小,或者用形式化的语言来说,任意(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

Cat命令很好用

在Linux下,有一个cat命令,它的作用是显示某个文本文件的内容。比如“cat a.txt”,就会把a.txt的内容全部显示出来。它是最简单的命令之一,甚至我觉得它只用getchar()和putchar()两个函数就实现了这个功能。

事实上,我以前基本不会去使用这条命令,因为它显示完文件就结束了,这意味着如果文件很长,而终端不能保存很多字符的话,几页屏一下子就刷过去了,根本什么都看不到。使用得更多的是less命令和more命令,more命令可以向下滚屏但是不能向上,less命令既能向下滚屏也能向上,因此比纯粹的cat命令好用得多。

但是最近在学C语言的时候,发现cat命令好用之处就在于它的纯粹。在《The C Programming Language》中,尤其是第一章里,有很多处理字符文本的小程序,比如去掉C语言源文件的注释。程序被设计为键盘输入,我们当然可以手动输入几行去简单验证程序的正确性,但做完之后还是很想直接找个源文件试试。这时cat命令就派上用场了,使用cat输出源文件,再用管道传给程序作为输入,最后可以看到结果是否正确,比如“cat a.c | b.out”。其实more和less的道理也是一样的,如果要输出文本内容,还是要依靠cat,比如“cat a.txt | less”。

Notepad++

前几天用了Notepad++,发现还不错,迟点有机会再介绍。

Alt键输入ASCII码

最近在看《The C Programming Language》,在第一章的时候有一个字符流的程序,然后在测试的时候需要输入各种字符去测试。一般的可见字符当然没问题,不过有些特殊字符还真的不容易输入,因为在键盘模式下面的字符流是比较特殊的。

首先,如果在Linux下的话,要使当前输入的东西作为字符流交给程序处理,有两种办法。第一个方法是按下Enter键,它会发出命令把当前行加上’\n’作为字符流交给程序处理,第二种方法是按Ctrl+D,这是主动发送命令结束本次字符流,如果刚好在一个空行按Ctrl+D,它还会发出EOF文件结束标志。所以如果在Linux下做那本书的实验,很多情况就要按Ctrl+D。

在Windows下也类似,但是按回车的时候返回两个字符,分别是’\r’和’\n’,就是回车和换行。而结束字符流采用的是组合键Ctrl+Z。

ASCII

在Windows下还有一个好处,就是可以用Alt键输入ASCII字符,当然是可打印字符才能输出出来,像’\b’这种退格符就没有办法了。方法是先按下Alt键不放,在小键盘输入ASCII码,然后放Alt,就成功了。如上图所示,如果输入65,就会显示一个A,这种方法是在NumLock键生效的情况才有用。假如NumLock键关闭了,可以使用Alt+Fn的方式,一样可以。

据说Alt键不仅可以输入ASCII,还可以输入Unicode,记得以前QQ流行过这种游戏。准备吃饭,观赏嫦娥。