问题标签 [clrs]

这是我正在寻找答案的问题：

数组 A[1...n] 包含从 0 到 n 的所有整数，除了一个。通过使用辅助数组 B[0...n] 记录哪些数字出现在 A 中，很容易在 O(n) 时间内确定丢失的整数。然而，在这个问题中，我们不能访问 A 中的整个整数一次操作。A 的元素以二进制表示，我们可以用来访问它们的唯一操作是“获取 A[i] 的第 j 位”，这需要恒定的时间。证明如果我们只使用这个操作，我们仍然可以在 O(n) 时间内确定丢失的整数。

我想到了这种方法：如果我没有上述获取限制，我会取所有数字并将它们一起进行 XOR。然后将结果与 1..n 中的所有数字进行异或运算。这将是我的答案。在这个问题中，类似地，我可以对数组中的所有元素在 log(n+1) 位的距离上重复异或不同数字的位，然后将它们与元素 1...n 异或，但复杂性出现在我看来是 O(nlogn)。

如何实现 O(n) 复杂度？谢谢

我一直在阅读 CLRS 并遇到了编写一个过程 Rand(a,b) 的问题，该过程使用 Rand(0,1) 以 50% 的概率生成 0 或 1 的过程 Rand(0,1) 随机均匀地在 a 到 b 之间生成一个随机数.

我想到了以下解决方案，时间为 O(b)：

请为此提出更好的方法。

我正在尝试将 3 个 4s 插入一个空的 B 树。t = 3。我在网上尝试了一些小程序，但所做的只是插入 4 一次，然后删除 4。它是在 CLRS 中实现的方式，因为我没有完全理解它们的伪代码。

这是来自 CLRS 的问题 2-1.b。我不明白如何在 n*lg(n/k) 中合并 n/k 个大小为 k 的数组。我能想出的最佳解决方案是通过在每个子列表的 min 元素中搜索 min 元素来填充大小为 n 的最终数组的每个条目。这导致 O(nk)。在指定时间内完成它的算法是什么？

现在我正在阅读算法介绍，快速排序一章。它说尾递归可用于优化。

但是，如果每次迭代的主元数为 [1,n-1] [n]，则上述代码的堆栈深度将为 O(n)。

我在上面的代码中理解的是，它将首先处理长度较小的子数组。但是为什么它可以减少到 O(lgn) 呢？如果每次枢轴仍然是 [1,n-1] [n]，我认为它会保持 O(n) 堆栈深度。

这是我要解决的练习CLRS的问题 10.3-4

通常希望在存储中保持双向链表的所有元素紧凑，例如使用多数组表示中的前 m 个索引位置。（在分页的虚拟内存计算环境中就是这种情况。）解释如何实现过程 ALLOCATE OBJECT 和 FREE OBJECT 以使表示紧凑。假设在链表本身之外没有指向链表元素的指针。（提示：使用堆栈的数组实现。）

到目前为止，这是我的解决方案

现在，问题是，如果是这样的话，我们就不需要链表了。如果删除是 O(n)，我们可以使用普通数组来实现它。其次，我也没有使用堆栈的数组实现。那么问题在哪里呢？我应该如何开始？

我正在阅读 CLRS，它说 heapsort 是

MAX_HEAPIFY 是O(lg n). 这本书说它运行了 MAX-HEAPIFYn次，因此是O(n lg n)时候了。

但是，如果堆的大小每次迭代都缩小 1，不是O(lg n!)吗？

会的lg 1 + lg 2 ... + lg(n-1) + lg (n) = lg(n!)，对吧？

我正在尝试在 Cormen 等人的算法简介中做这个练习，这与 Disjoin Set 数据结构有关：

假设我们希望添加操作PRINT-SET(x)，给定一个节点并以任意顺序x打印 集合的所有成员。x展示我们如何向不相交集森林中的每个节点添加一个属性，从而使PRINT-SET(x)时间与的集合的成员数成线性关系x，并且其他操作的渐近运行时间保持不变。假设我们可以在 O(1) 时间内打印出集合中的每个成员。

现在，我很确定需要的属性是一个尾指针，所以它可以跟踪孩子。

由于不相交的集合结构已经有一个父属性，find-set(x)可以很容易地打印出一个方向的节点。但是现在，有了一个尾指针，让我们也转向另一个方向。

但是，我不确定如何编写算法来做到这一点。如果有人可以用伪代码帮助我，那将不胜感激。

我正在阅读CLRS并遇到了一行“斐波那契堆延迟尽可能长的工作”。但是延迟工作实际上意味着什么，以及这与性能有何关系。

在霍夫曼编码算法中，有一个引理说：

最优二元前缀码对应的二叉树是满的

但我不知道为什么。你如何证明这个引理？