令 A
为已按升序排序的 n
整数数组。
令 B
为未排序的 m
整数数组。
我们知道 A
中的整数集与 B
中的整数集不相交。描述一种生成数组的算法,其中所有 n + m
整数均已按升序排序。您的算法应在 O(n + m log m)
时间内终止。
我知道这应该类似于合并排序,但是 O(n+mlogm)
中的 n+m
让我失望了。谁能解释一下?
最佳答案
我认为你应该先对 B 数组进行排序:O(mlogm)
之后你有两个排序的数组,你需要合并它们,这将花费:O(n+m)
现在整个过程是 O(mlogm + (n+m) )
等于 O(mlogm)
。
关于arrays - 合并排序变体 n+m,困惑,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39481937/