O(n log n)时间复杂度和O(1)空间复杂度的算法与O(n)时间复杂度和O(n)空间复杂度的算法比较。
我很想知道哪种算法更好： O(n log n)时间复杂度和O(1)空间复杂度的算法 O(n)时间复杂度和O(n)空间复杂度的算法 在大多数情况下，可以通过牺牲空间来将时间复杂度从O(n log n)降至O(n)。那么哪种算法更好呢？ 我该如何在这两个参数之间做出决定？ 例如：数...
在数组中查找连续的范围
你有一个整数数组，需要输出包含数组中所有数字的最大区间。这些数字可以按任意顺序出现。例如，假设给定的数组为：{2, 10, 3, 12, 5, 4, 11, 8, 7, 6, 15} 我们在这里找到了两个（非平凡的）范围，这些范围中所有的整数都出现在数组中，即 [2,8] 和 [10,12]。...
关于数组中的原地合并
我看到了以下问题。 给定一个包含n个元素和一个整数k，其中k<n。已经排好序的元素{a0...ak}和 {ak+1...an}。请提供一种时间复杂度为O(n)，空间复杂度为O(1)的算法进行排序。 在我看来，似乎无法以O(n)时间复杂度和O(1)空间复杂度完成此任务。实际上，这个问题...
为什么基数排序的空间复杂度为O(k + n)？
考虑一个由n个数字组成的数组，最大有k位数（参见Edit）。考虑来自这里的基数排序程序：def radixsort( aList ): RADIX = 10 maxLength = False tmp, placement = -1, 1 while not maxLengt...
检查具有退格的字符串是否相等的高效算法？
我最近在一次面试中被问到这个问题： 给定两个字符串 s 和 t，当它们都被输入到空文本编辑器中时，如果它们相等，则返回 true。# 表示退格字符。 Input: S = "ab#c", T = "ad#c" Output: true Explanation: Both S and T...
寻找一个出现次数为偶数的数字
给定一个数组，其中除一个数的出现次数为偶数外，每个数字的出现次数都是奇数。找到出现次数为偶数的数字。 例如：1, 1, 2, 3, 1, 2, 5, 3, 3 输出结果应为：2 下面是限制条件： 数字不在范围内。 原地操作。 所需时间复杂度为O（N）。 数组可能包含负数。 数组未排序。 ...
如何确定算法的内存和时间复杂度？
我不擅长确定时间和内存复杂度，希望有人能帮助我。这里有一个算法，但我不确定它的时间和内存复杂度是什么。Function sample(k) IF k < 2 Return 0 Return 1 + sample(k/2) 它的时间和空间复杂度是多少，为什么？ 谢谢
如何使用O(1)的辅助存储空间删除二叉树中所有节点？
删除二叉树中所有节点的标准算法使用沿着这些线路的后序遍历遍历节点： if (root is not null) { recursively delete left subtree recursively delete right subtree delete root } ...
在整数数组中查找重复项
这是一道面试题。 我得到了一个由范围在[1,n]内的n+1个整数组成的数组，该数组具有k (k≥1)个重复元素，每个重复元素可以出现多次。任务是以最佳时间和空间复杂度找到出现多次的数组元素。 经过长时间的思考，我自豪地提出了一个时间复杂度为O(nlogn)、空间复杂度为O(1)的解决方案。...
在线性时间和原地进行的排序
假设有n个记录，其键值范围为1到k。 编写一个算法，在O(n+k)时间内就地对记录进行排序。 您可以在输入数组以外使用O(k)的存储空间。 你的算法是稳定的吗？ 如果我们使用计数排序，可以在O(n+k)时间内完成，且具有稳定性，但它不是就地排序。 如果k = 2，则可以就地排序，但它不...