求一个数据结构基础算法思想!
正写到一个数据结构程序题...
二维数组A[m][n],每行每列都按从小到大排列,求数组中值为x的元素的行列号,比较次数不能超过m+n次(设x在A中存在)...
我想了想
1 3 4 6
2 7 8 9
5 9 11 12
8 10 12 13
如果按二分法查找...多写几行的时候最坏情况肯定超过m+n次
我还试着用用两个变量控制行列的比较范围,不过好像也不行...
想不出来了,所以来这里请教...第一次来CSDN上问问题...希望能帮忙解决,谢谢了!
[解决办法]
这其实是一排序二叉树
1－> 3－> 4－> 6
/\
|
2-> 7-> 8-> 9
/\
|
5-> 9-> 11-> 12
/\
|
8-> 10-> 12-> 13
......
从A[m][0] 开始比较
深度是m+n-1
比较次数不会超过m+n
[解决办法]
这和算法导论的一个课后题一样，lz所处理的矩阵被称为所谓的 "Young tableaus "，这是我以前写的算法的注释，直接贴过来了。。。
find operation is somewhat complex. First of all, in Young tableaus, the following facts hold
1.Given an element e located in (i, j), all the elements loacated in (x, y) which x <= i and y <= j are smaller than or equal to e.
2.Given an element e located in (i, j), all the elements loacated in (x, y) which x > = i and y > = j are larger than or equal to e.
The algrithm of find is based on the facts above. Assume that we need to find value e in Young tableaus. First, we search the value in the matrix diagonally. If we find it in principal diagonal, we just return it, else, we can find x, which satisfying (x, x) > e > (x - 1, x - 1)
Now, wo divide the matrix into four parts. The elements in left-top part (the elements located in (i, j) which i <= x and j <= x) are smaller than or equal to (x - 1, x - 1) which is smaller than e, and similarly, the right-bottom part are larger or equal to (x, x) which is larger than e. Hence, wo need only search the value in left-bottom part and right-top part. We consider each part a new matrix, and repeat the process above.
[解决办法]
dollybol()
我昨天还想到了一个办法,A[m][n]就是从第一个开始(i=0,j=0) A[i][j] 先扫描第一列,如果需要找的元素(e),比第一列的下一个元素比e小,并且 i+1 在m范围内,那么i++;否则j+1如果在n的范围内,那么j++;同样,如果在这个比较的过程中行的下一个元素比e大,那么i--... ...直到找出来......
这个方法的最坏情况好像正好是比较了m+n次...但是在写算法的时候感觉非常复杂...不怎么好控制if语句... ...我等会在写看看...
-------------------------------------------------
这个在最坏情况下应该比 m+n 大，比如下面要查找 9
1 3 4 9
2 4 6 10
5 7 11 12
8 10 12 13
另外，如果有重复时，这个方法只能查找到一个 x
fflush(stdin) 的方法不错，可以找到所有的 x，不知道你说的
“但是如果行列在不相等,并且相差比较大的情况下呢?先查找对角线似乎不行吧!”
是什么意思
[解决办法]
hellothinker()
排序二叉树...有鉴定........我也试试...
-------------------------------------
不是排序二叉树
[解决办法]
dollybol()
按照你的办法看来 只能应用这样的行列格式哦 ,该矩阵转置 的话就不行了哦 ,
这样看来还使用搜索二叉树的办法比较好,这个方法抓住了一个规律哦.
而且实现起来不是太难, 第一个元素的选择可以是a[m][0],也可以是A[0][N],
看起来满不错的
