个人中心
文章发布
退出
作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误，当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
26
4
假设您有一个合并函数，它将在 O(s1+s2) 时间内合并(找到并集)大小为 s1 和 s2 的两个列表 L1 和 L2。合并大小为 s1、s2、...、sk 的 k 个列表的最佳方法是什么？
我认为我们应该首先对 s1, ..., sk 进行排序，然后对对应于最小两个大小的前两个列表进行排序。当这些被合并时，我们找到它们的大小在排序的大小列表中的位置并继续这个过程，直到我们最终得到一个列表。
我在两件事上遇到了麻烦:1. 这是否确实是最优的(是否有另一种方法可以更快地返回)？ 2. 合并时列表大小发生变化，如何分析运行时间？
最佳答案
这恰好与为由k 的字母表组成的字符串寻找最佳可变长度位编码的问题相同。具有已知频率的符号 s<sub>1</sub>, s<sub>2</sub>, … s<sub>k</sub> .你的算法正是Huffman algorithm ，并且您会在任何有关算法的教科书(以及许多在线资源)中找到最优性证明，因为它是具有简单正确性证明的贪婪算法的经典案例。
双向合并的重复应用会产生一个二叉树，其中每个节点都是一个合并。给定那棵树，任何叶子对整体合并总成本的贡献是该叶子的权重乘以它在树中的深度。 (每个节点都是一个合并，叶子中的值恰好参与从叶子到根的路径中的合并；此类合并的数量是树中叶子的深度。)类似地 - 或相同地 - -，一个哈夫曼编码的比特串的总长度是符号的权重(频率)与构造树中该符号对应的叶子深度的乘积之和。
算法的一个小改进(编写霍夫曼树构建器的人经常错过):有必要对权重进行排序 s<sub>1</sub>, s<sub>2</sub>, … s<sub>k</sub> ，但这是唯一需要的类型。从那里开始，算法总是选择两个最低的节点并将它们相加。结果总和的大小必须是单调非递减的(如果总和小于前一个总和，则前一个总和不可能是两个最小元素的总和)。所以你可以把总和放在一个队列中；在每一步中，您都可以从已排序的叶子数组或(隐式)已排序的节点队列中选择两个最小的元素。
这可以通过用节点队列覆盖叶数组来进一步优化。 (然后队列从数组底部向顶部增长；证明队列顶部永远不会超过数组底部是相当简单的。)
关于algorithm - 合并 k 个列表的最佳方式是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26199864/
26
4
0
我一直在阅读有关汇编函数的内容，但对于是使用进入和退出还是仅使用调用/返回指令来快速执行，我感到很困惑。一种方式快而另一种方式更小吗？例如，在不内联函数的情况下，在汇编中执行此操作的最快(stdcal
我正在处理一个元组列表，如下所示: res = [('stori', 'JJ'), ('man', 'NN'), ('unnatur', 'JJ'), ('feel', 'NN'), ('pig',
最近我一直在做很多网络或 IO 绑定(bind)操作，使用线程有助于加快代码速度。我注意到我一直在一遍又一遍地编写这样的代码: threads = [] for machine, user, data
假设我有一个名为 user_stats 的资源，其中包含用户拥有的帖子、评论、喜欢和关注者的数量。是否有一种 RESTful 方式只询问该统计数据的一部分(即，对于 user_stats/3，请告诉我
我有一个简单的 api，它的工作原理是这样的: 用户创建一个请求 ( POST /requests ) 另一个用户检索所有请求 ( GET /requests ) 然后向请求添加报价 ( POST /
考虑以下 CDK Python 中的示例(对于这个问题，不需要 AWS 知识，这应该对基本上任何构建器模式都有效，我只是在这个示例中使用 CDK，因为我使用这个库遇到了这个问题。): from aws
Scala 中管理对象池的首选方法是什么？ 我需要单线程创建和删除大规模对象(不需要同步)。在 C++ 中，我使用了静态对象数组。 在 Scala 中处理它的惯用和有效方法是什么？ 最佳答案 我会把它
我有一个带有一些内置方法的类。这是该类的抽象示例: class Foo: def __init__(self): self.a = 0 self.b = 0
返回和检查方法执行的 Pythonic 方式 我目前在 python 代码中使用 golang 编码风格，决定移动 pythonic 方式 例子: import sys from typing imp
我正在开发一个 RESTful API。其中一个 URL 允许调用者通过 id 请求特定人员的记录。 返回该 id 不存在的记录的常规值是什么？服务器是否应该发回一个空对象或者一个 404，或者其他什
我正在使用 pathlib.Path() 检查文件是否存在，并使用 rasterio 将其作为图像打开. filename = pathlib.Path("./my_file-name.tif") 但
我正在寻找一种 Pythonic 方式来从列表和字典创建嵌套字典。以下两个语句产生相同的结果: a = [3, 4] b = {'a': 1, 'b': 2} c = dict(zip(b, a))
我有一个正在操裁剪理设备的脚本。设备有时会发生物理故障，当它发生时，我想重置设备并继续执行脚本。我有这个: while True: do_device_control() device
做组合别名的最pythonic和正确的方法是什么？ 这是一个假设的场景: class House: def cleanup(self, arg1, arg2, kwarg1=False):
我正在开发一个小型客户端服务器程序来收集订单。我想以“REST(ful)方式”来做到这一点。 我想做的是: 收集所有订单行(产品和数量)并将完整订单发送到服务器 目前我看到有两种选择: 将每个订单行发
我知道在 Groovy 中您可以使用字符串调用类/对象上的方法。例如: Foo."get"(1) /* or */ String meth = "get" Foo."$meth"(1) 有没有办法
在 ECMAScript6 中，您可以使用扩展运算符来解构这样的对象 const {a, ...rest} = obj; 它将 obj 浅拷贝到 rest，不带属性 a。 有没有一种干净的方法可以在
我有几个函数返回数字或None。我希望我的包装函数返回第一个不是 None 的结果。除了下面的方法之外，还有其他方法吗？ def func1(): return None def func2(
假设我想设计一个 REST api 来讨论歌曲、专辑和艺术家(实际上我就是这样做的，就像我之前的 1312414 个人一样)。 歌曲资源始终与其所属专辑相关联。相反，专辑资源与其包含的所有歌曲相关联。
这是我认为必须经常出现的问题，但我一直无法找到一个好的解决方案。假设我有一个函数，它可以作为参数传递一个开放资源(如文件或数据库连接对象)，或者需要自己创建一个。如果函数需要自己打开文件，最佳实践通常
我是一名优秀的程序员,十分优秀！