wayne 发表于 2010-6-1 11:48:27

百度HR算法设计题

1．给定如下的n*n的数字矩阵，每行从左到右是严格递增， 每列的数据也是严格递增

1 2 3

3 5 6

4 8 9

现在要求设计一个算法， 给定一个数k 判断出k是否在这个矩阵中。 描述算法并且给出时间复杂度（不考虑载入矩阵的消耗）

wayne 发表于 2010-6-1 12:02:48

题目应该很简单，我自己做的，不知道是不是log(n)*long(n)

qianyb 发表于 2010-6-1 12:23:49

本帖最后由 qianyb 于 2010-6-1 12:29 编辑

先用二分查找到小于k的最大行，再用二分法查找，复杂度应该是2log_2n

wayne 发表于 2010-6-1 13:00:41

我是按对角线进行二分查找，找出k所在的行或列m，然后分别对这个m行和m列余下的部分再进行二分查找，所以平均复杂度应该是O(logn*logn),

qianyb 发表于 2010-6-1 13:10:25

按你的方法，平均复杂度也是$2log_2n$，不过你的方法在编程上处理时比我的方法复杂

wayne 发表于 2010-6-2 09:08:58

3# qianyb


最大行怎么找出来的？

litaoye 发表于 2010-6-2 11:10:57

复杂度应该是O(n)的，就是一个杨氏矩阵的问题。2log2n做不到

qianyb 发表于 2010-6-2 11:53:35

本帖最后由 qianyb 于 2010-6-2 14:28 编辑

我题目理解错了，以为下一行的数据都比上一行大。就算上一行有的数据比下一行大，但复杂度还是log_2n不过代码的控制复杂了些
算法思路是

先从（1，1）开始按对角线查找小于k的最大行和大于k的最小行,即（x,x)>k,(x+1,x+1)<k,这是k可能的范围是矩形(x+1,1)，(n,x)和矩形（1,x+1),(x,n)范围内，在这两个范围内再次以对角线方式进行查找小于k的最大行和大于k的最小行，最后缩小到每个矩形为1时结束

shshsh_0510 发表于 2010-6-2 13:57:55

如果只简单的判断矩形中间元素，那么复杂度应该是$n*lg(n)$吧。
To litaoye：O(n)的法子是什么？

qianyb 发表于 2010-6-2 14:29:15

是查找元素k在不在矩阵中
页: [1] 2 3
查看完整版本: 百度HR算法设计题