Chinaunix

标题: 关于查找二维数组的最大值 [打印本页]

作者: riryka 时间: 2017-06-20 23:44
标题: 关于查找二维数组的最大值
基本方法是，双层循环，置一个初始的最大值，然后轮流判断。除了这种方法外，还有其他高效的方法吗

作者: 潜水一厮 时间: 2017-06-21 00:24
提示: 作者被禁止或删除内容自动屏蔽

作者: yulihua49 时间: 2017-06-21 15:23
本帖最后由 yulihua49 于 2017-06-21 15:40 编辑

潜水一厮发表于 2017-06-21 00:24
你不换数据结构，不管用什么方法总要把数据遍历一遍吧

如果只查一次，也就那样了。如果数组动态变化，并多次、频繁的查，还是建议更好的数据结构。

作者: folklore 时间: 2017-06-21 16:04
不遍历一次你怎么知道下一个被忽略的数不是最大的？

作者: yulihua49 时间: 2017-06-21 19:10
本帖最后由 yulihua49 于 2017-06-21 19:16 编辑

folklore 发表于 2017-06-21 16:04
不遍历一次你怎么知道下一个被忽略的数不是最大的？

把每个节点地址和值放到二叉树。如果动态数据也要对二叉树进行调整。
那么树的最大值就可以了。
最好是平衡树。multimap就很好用。

typedef struct node ｛
ini i;int j;

double V; //key
} node;

作者: lxyscls 时间: 2017-06-22 09:26
回复 5# yulihua49

要是能用其他数据结构，楼主也不会提这个问题吧
另外就是既然始终要的是最大值，用Max Heap不就好了，getMax永远都是O(1)

作者: yulihua49 时间: 2017-06-24 23:31

lxyscls 发表于 2017-06-22 09:26
回复 5# yulihua49

要是能用其他数据结构，楼主也不会提这个问题吧

只要最大值，你这个办法好。

作者: shang2010 时间: 2017-07-13 14:09
如果只查一个最大值，最好的数据结构是堆，配套堆排序

作者: lxyscls 时间: 2017-07-13 14:54
回复 8# shang2010

堆排序其实只是堆的衍生品，堆并不是为了解决排序问题产生的

作者: cjaizss 时间: 2017-07-21 12:39
回复 1# riryka

乱序存储下，没有好办法

作者: shang2010 时间: 2017-07-21 13:02
本帖最后由 shang2010 于 2017-07-21 13:04 编辑

现在想想最简单的路子。。。可以再添加一个变量，记录这个最大值的坐标，下次就省事了，不是么

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)