x*****g 发帖数: 3463 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: xlhuang (十里闲情), 信区: Programming
标 题: 求教:多个有序数组怎么合并最快?
发信站: BBS 未名空间站 (Mon Jul 11 09:51:07 2011, 美东)
多个有序数组合并成一个有序数组。各数组长度不同。所有数组的所有元素都是唯一的。
就是说,任何数组中的任何元素与任何其他数组中的任何元素都不会相同。
另外,如果每个元素还带有一个属性,要随着元素移动,怎么办?建个结构?
有没有更好的办法?
谢谢! | l********a 发帖数: 1154 | | x*****g 发帖数: 3463 | | l********a 发帖数: 1154 | 4 每个元素还带有一个属性,要随着元素移动
要么struct,要么2个数组,一个放属性,一个放元素 | I******c 发帖数: 163 | 5 两两合并比较好。合并的时候只要比较就可以了。当然你可以通过求rank来合并。你要
的是顺序算法还是并行算法?并行算法可能还有些小技巧可以使用。 | l****u 发帖数: 4594 | 6 很大吗? 不大的话,直接空间换时间,哈希;
的。
【在 x*****g 的大作中提到】 : 【 以下文字转载自 Programming 讨论区 】 : 发信人: xlhuang (十里闲情), 信区: Programming : 标 题: 求教:多个有序数组怎么合并最快? : 发信站: BBS 未名空间站 (Mon Jul 11 09:51:07 2011, 美东) : 多个有序数组合并成一个有序数组。各数组长度不同。所有数组的所有元素都是唯一的。 : 就是说,任何数组中的任何元素与任何其他数组中的任何元素都不会相同。 : 另外,如果每个元素还带有一个属性,要随着元素移动,怎么办?建个结构? : 有没有更好的办法? : 谢谢!
| R*******n 发帖数: 162 | 7 标准做法是 各个数组的头一个元素都拿出来建一个heap
O(log(L)N), L 是数组数, N是所有元素的数目
的。
【在 x*****g 的大作中提到】 : C
|
|