个人中心
文章发布
退出
作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误，当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
25
4
我遇到了以下问题。
给定一个包含 n 个元素的数组和一个整数 k，其中 k <n。元素 {a0...ak} 和{ak+1...an} 已经排序。给出一个在 O(n) 时间和 O(1) 空间内排序的算法。
在我看来，它不可能在 O(n) 时间和 O(1) 空间内完成。问题似乎真的是在询问如何就地执行合并排序的合并步骤。如果可能的话，不会以这种方式实现合并排序吗？我无法说服自己，但需要一些意见。
最佳答案
This似乎表明可以在 O(lg^2 n) 空间中进行。我看不出如何证明在恒定空间中合并是不可能的，但我也看不出如何去做。
编辑:Chasing references，Knuth Vol 3 - Exercise 5.5.3 说“L.Trabb-Pardo 的一个相当复杂的算法为这个问题提供了最好的答案:可以在 O(n) 时间内进行稳定合并并在 O(n) 时间内进行稳定排序O(n lg n) 时间，仅使用 O(lg n) 位辅助内存用于固定数量的索引变量。
更多references我还没有读过。感谢您提出一个有趣的问题。
进一步编辑:This article声称Huang和Langston的文章有一种算法，可以在时间O(m + n)中合并大小为m和n的两个列表，所以你的问题的答案似乎是肯定的。不幸的是我无法访问这篇文章，所以我必须相信二手信息。我不确定如何将此与 Knuth 关于 Trabb-Pardo 算法是最优的声明相协调。如果我的生命取决于它，我会和 Knuth 一起去。
我现在看到这已被问及更早的 Stack Overflow question一个number次。我不忍心将其标记为重复。
黄 B.-C.和 Langston M. A.，实用就地合并，Comm。 ACM 31 (1988) 348-352
关于arrays - 关于数组中的就地合并，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3285756/
25
4
0
我正在尝试解决以下问题: We are given an array containing ‘n’ objects. Each object, when created, was assigned a
考虑以下代码: a=(1 2 3) a='seven' export a declare -p a 输出(来自declare)是: declare -ax a='([0]="seven" [1]="2
我正在尝试将 ['1','2','3','4'] 转换为 [1,2,3,4]我想就地进行此转换。有可能做到吗？如果不是，最佳解决方案是什么。 最佳答案 我觉得用map比较好对于这类任务。这会创建迭代器
好的，所以我之前发布了关于尝试(没有任何预建函数)删除额外空间的信息 "this is a test"会回来的 "this is a test" Remove spaces from a strin
我有一个名为Media的插件，该插件应负责图像大小调整等工作。 它具有以下依赖性: dependencies { compile group: 'org.ccil.cowan.tagsoup'
我需要将一个大字符串向左“移动”X 个空格。它太大了，无法放入内存，所以我需要就地做。我需要使用最少量的系统调用来完成此操作。 我知道我可以使用缓冲区并重用内存来最大限度地减少内存消耗，然后使用 fs
我想知道是否可以在不需要临时数组的情况下通过 Cholesky 分解获得矩阵的逆。截至目前，我可以在不使用临时数组的情况下进行 cholesky 分解，但从那里我还没有想出一种方法来获得原始矩阵的逆矩
是否有任何用于 Javascript 的就地编辑插件..像 firebug 之类的东西，它对即时 CSS 编辑和预览非常有用，但不允许就地 JS 编辑..那么，有没有我们可以立即更新和更新的工具或插件
题目如下:给定一个 linked list，将备用 indices 移到 list 的后面 例如: input: : [0] -> [1] -> [2] -> [3] -> [4]
在我看来，std::copy_if 对于过滤容器非常有用: std::vector vec { 1, 2, 3, 4 }; auto itEnd = std::copy_if(vec.begin(),
在 C++ 中相交两个集合的标准方法是执行以下操作: std::set set_1; // With some elements std::set set_2; // With some othe
在 Python 中，字符串是不可变的。 逐个字符遍历字符串并对其进行修改的标准习语是什么？ 我能想到的唯一方法是一些与加入结果字符串相关的真正臭名昭著的黑客攻击。 -- 在 C 中: for(i
我有一个 ListBuffer。我想删除满足特定条件的所有元素。 我可以迭代它并删除每个元素。但是 Scala 对改变你正在迭代的列表有什么看法呢？它会起作用，还是会删除错误的元素/不返回所有元素？
我需要重新绑定(bind)两个大数据帧。现在我用的是 df 根据 nikola 的评论，这里是 ?rbindlist 的描述(v1.8.2 中的新增功能): Same as do.call("rbi
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题. 已关闭 3 年前。 Improve th
我在带有 LVS_EDITLABELS 的无模式 Win32 对话框中有一个小图标模式的 ListView 放。无论编辑是通过单击鼠标还是通过调用 ListView_LabelEdit() 以编程方式
所以基本上不能/允许创建一个新数组。除了实际更改和操作当前数组外，无法返回任何内容。您如何获取字符数组并简单地翻转/反转它们。 Starting array: ['P','e','r','f','e'
我不明白为什么下面的代码没有对 vector 的前两个元素进行排序: int main() { std::vector v = {2,1,3,1,2}; std::sort(v.beg
我有以下(简化的)代码: a = a[::3] b = b[::3] c = c[::3] d = d[::3] a,b,c,d,其实都是很复杂的表达式，所以我想这样写: for l in [a, b
可以对数组进行不依赖于数组秩的操作。迭代器也不总是合适的解决方案。给定数组 double[,] myarray = new double[10,5]; 实现以下工作流程是可取的: 将 Rank>1 的
我是一名优秀的程序员,十分优秀！