这个问题的更简单或更流行的版本是找到具有给定总和的三元组。但这一个提出了一个额外的条件。找到未排序数组中的所有三元组，使得
d[i]+d[j]+d[k] <= t; & d[i]<d[j]<d[k] where i<j<k
这是问题第一部分的解决方案。但是有人可以建议我们如何将它扩展到包括第二个条件。我能想到的唯一方法是在排序时执行自定义数据结构以存储原始元素索引以及数字。然后检查包含链接中提到的算法返回的每个三元组的索引是否有序。
问问题
6639 次
9 回答
5
首先，值得指出的是，最坏情况的复杂性不能优于O(n^3)，因为在最坏的情况下存在O(n^3)三元组，显然每个三元组至少需要恒定的时间来存储/打印它。还有一个非常简单明了的O(n^3)算法。
话虽这么说，这就是你如何用复杂的方法做到这一点，答案的大小在O(n^2 log n + k)哪里。k（虽然@saadtaame 声称具有相同的复杂性，但他的估计存在问题，请参阅他的答案下方的评论）。
首先，让我们修复一个元素，比如说a[i]. 现在让我们创建一个新数组b，其中包含来自 的所有元素a，它们的索引都大于i，值都大于a[i]。现在问题减少到找到两个索引j和k，b这样j < k和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，我们把所有的元素都放在右边 from5和更大的 to 上b，所以b = [7, 9, 8]。然后k将进行三个迭代：
b[k] = 7. 此时 treeSet 是空的，所以什么也没有发生，7并被添加到 treeSet 中。b[k] = 9. 此时 treeSet 有元素 7。它小于 9，但是 sum5 + 7 + 9 > 20，所以我们中断了对 treeSet 的迭代。我们放到9treeSet中，到现在包含的集合(7, 9)b[k] = 8. 我们遍历树集。对于元素 7，两个条件都满足 (7 < 8 and 5 + 7 + 8 <= 20)，因此(5, 7, 8)添加到答案中。对于元素 9，元素大于b[k]，所以我们打破。
然后循环k结束。
然后我们i向右移动一个元素。的内容b将完全相同，上述三个步骤几乎相同，只是在第二步中答案足够小，因此我们将屈服(3, 7, 9)和(3, 7, 8)。
然后当我们移动到下一个i时a[i] = 7，数组b将只包含两个元素[9, 8]，并且不会产生任何答案。
我建议用 Java 编写带有一些调试输出的代码，并尝试使用它来更好地理解它。
于 2015-02-03T00:53:30.167 回答
3
我认为它可以在 O(n^2logn) 时间内解决，使用 TreeMap 或 Sorted Map 概念。我尝试在 Java 中实现相同的功能，但概念保持不变。
import java.util.*;
public class Main
{
public static void main(String[] args) {
int arr[]={1,2,3,3,4,4,9,10,11,342,43};
int n=arr.length,t=98,cnt=0;
Arrays.sort(arr);
for(int k=2;k<n;k++)
{
TreeMap<Integer,Integer> ts1=new TreeMap<>();
for(int j=0;j<k;j++)
{
if(arr[j]==arr[k])
break;
int i=Math.min(t-arr[k]-arr[j],arr[j]); //try to get the number of elements less than arr[j] and target-arr[k]-arr[j]
cnt+=(ts1.lowerKey(i)==null?0:ts1.get(ts1.lowerKey(i)));
if(ts1.containsKey(arr[j]))
ts1.put(arr[j],ts1.get(arr[j])+1);
else
{
Integer val=ts1.lowerKey(arr[j]);
ts1.put(arr[j],1+(val==null?0:ts1.get(val)));
}
}
}
System.out.println(cnt);
}
}
请让我知道这对你有没有用。
于 2020-11-04T19:02:44.973 回答
2
求和小于或等于 k 的递增三元组：
# include <stdio.h>
void find3Numbers(int A[], int arr_size, int sum)
{
int l, r;
for (int i = 0; i < arr_size-2; i++){
for (int j = i+1; j < arr_size-1; j++){
for (int k = j+1; k < arr_size; k++){
if (A[i] + A[j] + A[k] <= sum)
printf("Triplet is %d, %d, %d\n", A[i], A[j], A[k]);
}
}
}
}
int main()
{
int A[] = {1, 2, 3, 4, 6};
int sum = 8;
int arr_size = sizeof(A)/sizeof(A[0]);
find3Numbers(A, arr_size, sum);
return 0;
}
输出 ：
Execution :
arr_size = 5
Step:1 i=0 and i<3 (arr_size-2)
j=1 and j<4 (arr_size-1)
k=2 and k<5 (arr_size)
A[0]+A[1]+A[2]<=sum --> 1+2+3 <=8 --> 6<=8 ( true )
k=3 and k<5
A[0]+A[1]+A[3]<=sum --> 1+2+4 <=8 --> 7<=8 ( true )
k=4 and k<5
A[0]+A[1]+A[4]<=sum --> 1+2+6 <=8 --> 9<=8 ( false )
j=2 and j<4
k=3 and k<5
A[0]+A[2]+A[3]<=sum --> 1+3+4 <=8 --> 8<=8 ( true )
k=4 and k<5
A[0]+A[2]+A[4]<=sum --> 1+3+6 <=8 --> 10<=8 ( false )
j=3 and j<4
k=4 and k<5
A[0]+A[3]+A[4]<=sum --> 1+4+6 <=8 --> 11<=8 ( false )
j=4 and j<4 (false)
Step:2 i=1 and i<3
j=2 and j<4
k=3 and k<5
A[1]+A[2]+A[3]<=sum --> 2+3+4 <=8 --> 9<=8 ( false )
k=4 and k<5
A[1]+A[2]+A[4]<=sum --> 2+3+6 <=8 --> 11<=8 ( false )
j=3 and j<4
k=4 and k<5
A[1]+A[3]+A[4]<=sum --> 2+4+6 <=8 --> 12<=8 ( false )
j=4 and j<4 (false)
Step:3 i=2 and i<3
j=3 and j<4
k=4 and k<5
A[2]+A[3]+A[4]<=sum --> 3+4+6 <=8 --> 13<=8 ( false )
j=4 and j<4 (false)
Step:4 i=3 and i<3 (false)
于 2017-04-22T12:51:33.577 回答
1
哈哈，很高兴看到我的博客被引用到这里。但是您链接的帖子解决了d[i]+d[j]+d[k] < t
我认为您应该清楚地询问您的数组是否已排序，那么您的问题是如何找到等于数组中特定总和的对的轻微扩展
因此，对于您的情况（假设数组已排序），您只需确保 i、j、k 始终按递增顺序排列。
因此，考虑到 N 个元素和一个目标 T，一个经典的昼夜方法（即 j、k 彼此靠近），您可以尝试：
for (int i = 0; i < N, i++) {
int j = i;
int k = N-1;
while (j < k) {
int currSum = i+j+k;
if (currSum < T) { // increase sum
j++;
}
else if (currSum > T) { // decrease sum
k--;
}
else {
System.out.println("Found triple: " + i + ", " + j + ", " + k);
j++;
}
}
}
//i, j, k 保证按升序排列。
如果数组没有排序，你可以做一个优化的蛮力。所以找到所有 i, j 使得 d[i] < d[j] 并且 i < j。然后在这些对中的每一个上尝试在 j 之后找到 ak。
于 2015-01-21T19:57:54.140 回答
1
我认为你可以做得比 O(n^2 log n + k) 稍微好一点。
假设你在位置 i。直到 i (1...i) 的所有元素都存储在一个 BST 中，而 i (1+1...n) 之后的所有元素都存储在第二个 BST 中。
在第一棵树中，找到最小元素 A[j] 使得 A[j]
现在，在第二棵树中找到最大的元素 A[k]，使得 A[k] < kA[i]-A[j]。如果 A[k]<=A[i] 停止。否则，打印 A[j],A[i],A[k]，并在第二棵树中设置 k = prev(A[k])。循环直到 A[k]<=A[i]。
在这一切的中间，做一个额外的比较。令 A[j1] = next(A[j])（即 A[j1] 是排序序列中的下一个元素）。如果对于 ak 如果它也遵循条件 A[j1]+A[i]+A[k] <=t，记下这样的最大 k。并且在下一次迭代中，直接使用这个 k 而不是二分查找。
最初从 i=2 开始，firstTree={A[1]}，secondTree = {A[3]..A[n]}。并且每当您增加 A[i] 时，将 A[i] 添加到 firstTree 并从第二个树中删除 A[i+1]。
总体时间复杂度：O(n^2+n*log(n)) + O(p) = O(n^2+p) 其中 p 是总结果的数量。
算法：
Initialization: firstTree={A[1]}, secondTree = {A[3]..A[n]}
For i = 2:(n-1) do:
j = getFirst(firstTree)
firstIter = true;
while(true)
if A[j]>=A[i] or A[j]+A[i]>t break
if firstIter:
k = binSearch(secondTree, t - A[i] -A[j])
firstIter=false
else
if bestk<0:
break;
k = bestk
bestk = -1
jnext = nextElement(firstTree, A[j]);
while (A[k]>A[i]):
print (A[j], A[i], A[k])
if bestk<0 and A[i]+A[jnext]+A[k] < t:
bestk = k;
k = prevElement(secondTree, A[k])
Add(firstTree, A[i])
Remove(secondTree, A[i+1])
请注意，每个 i 只调用一次 binSearch，并且对于一个 i，nextElement 只通过树一次（复杂度 O(n)）。内部 while 循环只被调用一次。所以整体复杂度是 O(n^2 + nlogn + p) 其中 p 是输出的数量。
编辑：因为如果我们发现一个没有结果的 j（即 j 没有解决方案），我们停止。我认为这个成本包含在 O(p) 本身中。所以最终的复杂度是 O(nlogn + p)。抱歉，我没有时间提供详细的证明。
于 2015-02-03T07:31:08.643 回答
0
我认为在这种情况下可以实现 n^2*logn 。
我们要做的是首先使用快速排序数字进行排序，这样可以避免额外的循环，并且默认情况下 i < j < k。
我的逻辑是 d[i] + d[j] + d[k] <= t ，所以 d[k] <= t - d[i] -d[j] 所以第一个循环将运行 1 到 n，第二个运行从 i + 1 到 n 和第 3 次，我们将对 (t - d[i] -d[j]) 进行二进制搜索并比较 d[i] < d[j] < d[k] 以避免重复。因此，通过这样做，我们可以获得 nlogn(sorting) + (n^2*logn) 的复杂度来求和。
所以我的电话是：
Arrays.sort(d);
for (int i = 0; i < d.length; i++) {
for (int j = i + 1; j < d.length; j++) {
int firstNumber = d[i];
int secondNumber = d[j];
int temp = t - firstNumber - secondNumber;
if ((firstNumber < secondNumber) && (secondNumber < temp)) {
int index = Arrays.binarySearch(d, temp);
if (index >= 0) {
......
}
}
}
}
}
于 2015-05-26T09:48:46.707 回答
0
这是c++版本
#include <bits/stdc++.h>
using namespace std;
vector<int> helper(vector<int> &A, int T)
{
vector<int> ans;
int N = A.size();
for (int i = 0; i < N; i++)
{
vector<int> B;
for (int j = i + 1; j < N; j++)
{
if (A[j] > A[i])
B.push_back(A[j]);
}
set<int> S;
set<int>::iterator it;
for (int k = 0; k < B.size(); k++)
{
for (auto it = S.begin(); it != S.end(); it++)
{
int sum = A[i] + *it + B[k];
if (*it >= B[k] || sum > T)
break;
cout << A[i] << " - " << *it << " - " << B[k] << endl;
ans.push_back(sum);
}
S.insert(B[k]);
}
}
return ans;
}
vector<int> helper1(vector<int> &A, int T)
{
vector<int> ans;
int N = A.size();
for (int i = 0; i < N - 2; i++)
{
for (int j = i + 1; j < N - 1; j++)
{
for (int k = j + 1; k < N; k++)
{
int sum = A[i] + A[j] + A[k];
if (sum <= T && A[i] < A[j] && A[j] < A[k])
{
cout << A[i] << " - " << A[j] << " - " << A[k] << endl;
ans.push_back(sum);
}
}
}
}
return ans;
}
void print(vector<int> &A)
{
for (int a : A)
cout << a << " ";
cout << endl;
}
int main()
{
vector<int> A({1, 4, 12, 3, 6, 10, 14, 3});
int T = 11;
vector<int> ans = helper(A, T); // O(n^2log n)
print(ans);
vector<int> ans1 = helper1(A, T); // )(n^3)
print(ans1);
return 0;
}
于 2021-04-25T05:34:25.027 回答
-1
如果修复 i 和 j，则必须在数组中找到一个小于或等于 的数字t - d[i] - d[j]。存储数组的第二个版本，其中每个元素也存储它的索引。按升序对该数组进行排序。
现在，对于所有i, j带有i < j（这只是两个嵌套的 for 循环）的对，您可以二进制搜索t - d[i] - d[j]; 如果存在这样的数字，则从左到右遍历所有数字，并检查它们的索引是否大于 j，如果是，则添加到输出中。复杂性是O(n*n*lg n + k)其中 k 是满足条件的输出数量。
编辑：OP 的第一篇文章=现在改为<=. 我更新了我的答案。
于 2015-01-21T20:13:35.823 回答
-1
有条件，i<j<k
你的立方体的一半不符合条件，所以你可以消除不需要的东西
for (int k = 0; k < N, k++)
{
for (int j = 0; j < k, k++)
{
if (d[j] < d[k]) continue;
for (int i = 0; i < j, i++)
{
if (d[k] < d[j]) continue;
if (d[i]+d[j]+d[k] <= t)
{
//valid result
}
}
}
}
于 2015-02-03T03:27:31.663 回答