找到增加的三元组,使得和小于或等于k

Question

这个问题的更容易或更流行的版本是找到具有给定总和的三元组.但是这个提出了额外的条件.找到未排序数组中的所有三元组

d[i]+d[j]+d[k] <= t;   & d[i]<d[j]<d[k] where i<j<k

这是问题第一部分的解决方案.但有人可以建议我们如何扩展它以包括第二个条件.我能想到的唯一方法是在排序时执行自定义数据结构以存储原始元素索引以及数字.然后检查索引是否符合所包含链接中提到的算法返回的每个三元组的顺序.

Answer 1

首先，值得指出的是，最坏情况的复杂性不能比 好O(n^3)，因为在最坏的情况下有O(n^3)三元组，显然每个三元组至少需要恒定的时间来存储/打印它。并且有一个非常简单明了的O(n^3)算法。

话虽如此，以下是您如何使用复杂性来做到这一点，答案的大小O(n^2 log n + k)在哪里k。（虽然@saadtaame 声称具有相同的复杂性，但他的估计存在问题，请参阅他的答案下方的评论）。

首先，让我们修复一个元素，比如a[i]。现在让我们创建一个新数组，b其中包含来自 的所有元素a，它们的索引都大于i且值都大于a[i]。现在问题简化为找到两个索引jand kin b，例如j < kand b[j] < b[k]。

为此，我们可以使用某种排序集，例如TreeSetJava 中的 a。我们将迭代 的所有可能值k，维护索引小于k中的所有元素TreeSet。由于TreeSet只包含与指数小于元素k不是（因为我们建立的方式），和更大i（因为b只包含这些元素），并进行排序，然后每一个元素q在TreeSet具有比小的值b[k]的形式回答三重(a[i], q, b[k]). 这是一个伪代码：

for i from 0 to size(a):
    b = empty array
    for j from i + 1 to size(a):
        if a[j] > a[i]:
            add a[j] to b
    treeSet = new TreeSet
    for k from 0 to size(b):
        for each element 'e' in the treeSet in sorted order: // (1)
            if e >= b[k] or a[i] + e + b[k] > t:
                break
            add (a[i], e, b[k]) to the answer // (2)
        add b[k] to the treeSet // (3)

这里如果我们返回的元素数小于O(n^2 log n)，那么算法的复杂度将为O(n^2 log n)。原因是该行(2)被精确执行了k几次，因此可以忽略（并且迭代一个 treeSet 已经在元素数量上摊销了线性时间），而内部循环的其余部分：初始化迭代器(1)并将元素添加到treeSetat(3)都是最多O(log n)操作。

编辑：这是一个小例子。假设数组是a = [5, 3, 7, 9, 8, 1]and t = 20。然后i首先指向5，我们把所有从右边5和大到的元素都放在b，所以b = [7, 9, 8]。然后k会做三个迭代：

1. b[k] = 7. 此时 treeSet 是空的，所以什么都没有发生，7并被添加到 treeSet 中。

2. b[k] = 9. 此时 treeSet 有元素 7。它小于 9，但是 sum 5 + 7 + 9 > 20，因此我们从 treeSet 上的迭代中断。我们放入9treeSet，到集合现在包含(7, 9)

3. b[k] = 8. 我们遍历 treeSet。对于元素 7，两个条件都满足 ( 7 < 8 and 5 + 7 + 8 <= 20)，因此(5, 7, 8)添加到答案中。对于元素 9 元素大于b[k]，所以我们打破。

然后循环k结束。

然后我们i向右移动一个元素。的内容b会完全一样，上面三步几乎是一样的，只是在第二步的时候答案足够小，所以我们会yield (3, 7, 9)and (3, 7, 8)。

然后当我们移动到下一个i时a[i] = 7，数组b将只包含两个元素，[9, 8]，并且不会产生任何答案。

我建议用 Java 编写一些调试输出，然后稍微玩一下以更好地理解它。