我需要帮助找到一个算法,它可以找到:
- 数组中的四个元素
- 这四个元素的和等于给定的数字X
- 时间复杂度为O(n^2*log(n))
最好提供伪代码或C、C++代码。
我需要帮助找到一个算法,它可以找到:
最好提供伪代码或C、C++代码。
你可以用O(n^2)的时间复杂度来解决。它适用于带有重复和负数的情况。
编辑:正如André在评论中提到的,这个算法使用哈希表来实现时间复杂度,可能会出现最坏情况(虽然比中彩票的概率还要小)。但是你也可以用平衡树(例如Java中的TreeMap)替换哈希表,从而得到稳定的O(n^2*log(n))解决方案。
哈希表sums
将存储所有可能的两个不同元素之和。对于每个总和S
,它返回一对索引i
和j
,使得a[i]+a[j]==S
且i!= j
。但是初始时它是空的,我们需要在运行过程中填充它。
for (int i = 0; i < n; ++i) {
// 'sums' hastable holds all possible sums a[k] + a[l]
// where k and l are both less than i
for (int j = i + 1; j < n; ++j) {
int current = a[i] + a[j];
int rest = X - current;
// Now we need to find if there're different numbers k and l
// such that a[k] + a[l] == rest and k < i and l < i
// but we have 'sums' hashtable prepared for that
if (sums[rest] != null) {
// found it
}
}
// now let's put in 'sums' hashtable all possible sums
// a[i] + a[k] where k < i
for (int k = 0; k < i; ++k) {
sums[a[i] + a[k]] = pair(i, k);
}
}
假设 X = a[1] + a[3] + a[7] + a[10]
。当 i = 7
,j = 10
,以及rest = a[1] + a[3]
(索引1和3将从哈希表中找到)时,可以找到这个总和。
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <math.h>
#include <map>
using namespace std;
struct Entry
{
int a;
int b;
};
int main () {
typedef vector<int> VI;
VI l(5);
l[0] = 1;
l[1] = 2;
l[2] = -1;
l[3] = -2;
l[4] = 5;
l[5] = 6;
sort(l.begin(), l.end());
int sumTo = 0;
typedef multimap<int, Entry> Table;
typedef pair<int,Entry> PairEntry;
Table myTbl;
// N
for (int i = 0; i < l.size(); ++i)
{
// N
for (int j = i+1; j < l.size(); ++j)
{
// Const
int val = l[i] + l[j];
// A is always less than B
Entry ent = {i, j};
myTbl.insert(PairEntry(val,ent));
}
}
pair<Table::iterator, Table::iterator> range;
// Start at beginning of array
for (Table::iterator ita = myTbl.begin();
ita != myTbl.end();
++ita)
{
int lookFor = sumTo - ita->first;
// Find the complement
range = myTbl.equal_range(lookFor);
// Const bound
for (Table::iterator itb = range.first;
itb != range.second;
++itb)
{
if (ita->second.a == itb->second.a || ita->second.b == itb->second.b)
{
// No match
}
else
{
// Match
cout << l[ita->second.a] << " " << l[itb->second.a] << " "
<< l[ita->second.b] << " " << l[itb->second.b] << endl;
return 0;
}
}
}
return 0;
}
遍历数组B(O(n^2)),对于值为(X-B[i])的元素进行快速搜索(O(log(n^2)) = O(log(n)))。可能有多个这样的元素(但不超过n^2个)。
4.1 遍历所有值为(X-B[i])的元素,使用索引k。
4.2 跳过S[B[k]]与S[B[i]]相交的元素B[k]。两个由两个数字组成的集合的交集可以在O(1)时间内计算。
4.3 如果k是一个元素的索引,其中B[i]+B[k]==X,并且S[B[k]]与S[B[i]]不相交,则集合S[B[k]]和S[B[i]]的和就是四个所寻找的数字。
性能为: O( n^2 + n^2*log(n^2) + n^2*log(n^2) ) = O( n^2 * log(n^2) ) = O( n^2 * log(n) )
在第四步中,当我们使用嵌套循环迭代B
的多个匹配元素时,两个嵌套循环的总迭代次数受到|B|
的限制,即O(n^2)。快速搜索不是通常的变体,而是找到具有最低索引的匹配元素的变体。(或者可以使用通常的bsearch
,因为我们可能已经落在了中间,所以要使用两个相邻的循环,在两个方向上检查元素。)
log(n^2)
等于2log(n)
,所以时间复杂度不会超过。但是这并没有考虑重复元素的情况,需要进行额外的检查来解决。例如给定数组 [1, 2, 3]
和所有和的组合 [ 1+2, 1+3, 2+3 ]
,可以用 4 + 5
得到期望的和 9
,但是其中的 3
被重复计算了。 - Anurag// find four numbers in an array such that they equals to X
class Pair{
int i;
int j;
Pair(int x,int y){
i=x;
j=y;
}
}
public class FindNumbersEqualsSum {
public static void main(String[] args) {
int num[]={1,2,3,4,12,43,32,53,8,-10,4};
get4Numbers(num, 17);
get4Numbers(num, 55);
}
public static void get4Numbers(int a[],int sum){
int len=a.length;
Map<Integer, Pair> sums = new HashMap<Integer, Pair>();
for (int i = 0; i < len; ++i) {
// 'sums' hastable holds all possible sums a[k] + a[l]
// where k and l are both less than i
for (int j = i + 1; j < len; ++j) {
int current = a[i] + a[j];
int rest = sum - current;
// Now we need to find if there're different numbers k and l
// such that a[k] + a[l] == rest and k < i and l < i
// but we have 'sums' hashtable prepared for that
if (sums.containsKey(rest)) {
// found it
Pair p = sums.get(rest);
System.out.println(a[i]+" + "+a[j]+" + "+a[p.i] +" + "+a[p.j]+" = "+sum);
}
}
// now let's put in 'sums' hashtable all possible sums
// a[i] + a[k] where k < i
for (int k = 0; k < i; ++k) {
sums.put(a[i] + a[k],new Pair(i, k));
}
}
}
}
Result:
4 + 8 + 3 + 2 = 17
8 + 4 + 4 + 1 = 17
43 + 8 + 3 + 1 = 55
32 + 8 + 12 + 3 = 55
8 + -10 + 53 + 4 = 55
-10 + 4 + 8 + 53 = 55
1) 创建一个包含所有可能的数对和的数组 [O(N^2)]
2) 将此数组按升序排序 [O(N^2 * Log N)]
3) 现在,这个问题可以简化为在线性时间内找到一个已排序数组中两个数的和等于给定数字X。使用两个指针:一个从最小值开始的LOW指针,一个从最大值开始的HIGH指针。如果总和太低,则将LOW指针向前移动。如果总和太高,则将HIGH指针向后移动。最终它们将找到那一对或相互交叉(这很容易证明)。这个过程需要线性时间,即O(N ^ 2)
这样就得到了所需的O(N^2 * log N)的总时间。
注意:这种方法可以推广到解决M个数字的情况,时间复杂度为O(M * N^(M/2) * log N)。
-- 编辑 --
实际上,我的回答与Dummy00001的回答非常相似,只是最后的查找方法不同(尽管总体复杂度相同...)
sum=18
。并且 a = {2,3,4,5,7,9,10}
现在 a[0]+a[1]=5
和 a[2]+a[5]=13
,因此 a[0]+a[1]+a[2]+a[5]=18
。但是 a[1]+a[2]=7
和 a[0]+a[5]=11
因此 a[0]+a[1]+a[2]+a[5]=18
。因此,您的解决方案将打印这两个而不是1。那么您将如何解决这个问题。谢谢。 - Trying我编写了一个O(N^^2)的运行时间函数,它不使用哈希表,但可以处理负数和重复数字。我通过在整数数组中添加一个大正数(例如100)来处理负数,然后将目标调整为target += (4 * 100)
。当我找到结果时,我从结果中减去100。以下是我的代码和测试用例,请告诉我这是否具有O(N^^2)的时间复杂度。
struct maryclaranicholascameron{
int sum;
int component1;
int component2;
};
void Another2PrintSum(int arr[], int arraysize, int target){
int i(arraysize -1);
int j(arraysize -2);
int temp(target);
int temp2(0);
int m(0);
int n(0);
int sum(0);
int original_target(target);
for (int ctr = 0; ctr < arraysize; ctr++){
sum += arr[ctr];
}
for (int ctrn = 0; ctrn < arraysize; ctrn++){
arr[ctrn] += 100;
}
maryclaranicholascameron* temparray = new maryclaranicholascameron[sum + (arraysize *100)];
memset(temparray, 0, sizeof(maryclaranicholascameron) * (sum + 400));
for (m = 0; m < arraysize; m++){
for (n = m + 1; n < arraysize; n++){
temparray[arr[m] + arr[n]].sum = arr[m]+ arr[n];
temparray[arr[m] + arr[n]].component1 = m;
temparray[arr[m] + arr[n]].component2 = n;
}
}
target += (4 * 100);
original_target = target;
bool found(false);
while (i >= 0 && i < arraysize && found == false){
target -= (arr[i]);
while(j >= 0 && j < arraysize && found == false){
temp2 = target;
target -= (arr[j]);
if (i != j && temparray[target].sum == target &&
temparray[target].sum != 0 &&
temparray[target].component1 != i &&
temparray[target].component2 != i &&
temparray[target].component1 != j &&
temparray[target].component2 != j){
printf("found the 4 integers i = %d j = %d m = %d n = %d component1 = %d component = %d i %d j %d\n",
arr[i] - 100,
arr[j] - 100,
arr[temparray[target].component1] - 100,
arr[temparray[target].component2] - 100,
temparray[target].component1,
temparray[target].component2,
i,
j);
found = true;
break;
}
j -= 1;
target = temp2;
}
i -= 1;
j = i;
target = original_target;
}
if (found == false){
printf("cannot found the 4 integers\n");
}
delete [] temparray;
}
// test cases
int maryclaranicholas[] = {-14,-14,-14,-14,-12 ,-12, -12 ,-12 ,-11, -9,-8,-7,40};
Another2PrintSum(maryclaranicholas, 13,-2};
int testarray[] = {1,3,4,5,7,10};
Another2PrintSum(testarray, 6, 20);
temparray
只存储了1对索引,这些索引加起来等于特定的目标。如果在迭代过程中发现这一对会与最终循环中的另一对相交,但还有另一对不会怎么办?这基本上就是为什么"Sibshops"的答案使用了multi-map。 - user9989615public class Combination {
static int count=0;
public static void main(String[] args) {
int a[] = {10, 20, 30, 40, 1, 2,4,11,60,15,5,6};
int setValue = 4;
getCombination(a, setValue);
}
private static void getCombination(int[] a, int setValue) {
// TODO Auto-generated method stub
int size = a.length;
int data[] = new int[setValue];
createCombination(a, data, setValue, 0, 0, size);
System.out.println(" total combinations : "+count);
}
private static void createCombination(int[] a, int[] data, int setValue,
int i, int index, int size) {
// TODO Auto-generated method stub
if (index == setValue) {
if(data[0]+data[1]+data[3]+data[2]==91)
{ count ++;
for (int j = 0; j < setValue; j++)
System.out.print(data[j] + " ");
System.out.println();
}return;
}
// System.out.println(". "+i);
if (i >= size)
return;
// to take care of repetation
if (i < size - 2) {
while (a[i] == a[i + 1])
i++;
}
data[index] = a[i];
// System.out.println(data[index]+" "+index+" .....");
createCombination(a, data, setValue, i + 1, index + 1, size);
createCombination(a, data, setValue, i + 1, index, size);
}
}
示例输入:
int a[] = {10, 20, 30, 40, 1, 2,4,11,60,15,5,6};
输出::
10 20 1 60
10 30 40 11
10 60 15 6
20 30 40 1
20 60 5 6
30 40 15 6
11 60 15 5
total combinations : 7
这个问题可以简化为找到所有长度为4的组合。对于每个得到的组合,求和元素并检查它是否等于X。
听起来像是一道作业题。但这是我会做的。
首先对数字进行排序(这就是n*log(n))。
现在,创建指向列表的指针,并用前4个数字初始化它。一旦完成,您可以检查当前4个数字的总和与目标总和是否小于或等于。如果不是,您可以提前退出。现在,您只需要遍历列表的其余部分,交替地将指针替换为列表中的当前值。这只需要发生一次(或者最坏情况下4次),所以这就是另一个n,使得n^2*log(n)。
您需要跟踪一些逻辑,以了解您是否超过/低于您的总和以及下一步该怎么做,但我把它留给您作为家庭作业。
我不会完全回答你的问题,因为我认为这是一道作业题,而且我认为这很容易做到。但我确实知道你为什么难以得到答案,所以我会帮你一点忙。
首先,你应该研究递归。也就是说,从函数内部调用自身。
其次,你应该使用一个辅助函数,由你想要编写的函数调用。这个函数应该接受以下参数: - 一个数字数组 - 数组的长度 - 你想要找到总和为多少的成员的值 - 你想要求和的数组成员数量
这个函数将被你的其他函数调用,并传递一个4作为最后一个参数。然后它将调用自身,调整参数,尝试通过部分试错来找到结果。
经过进一步思考,我意识到这不是O(n^2),正如我之前声称的那样(我在中间步骤上粗略地忽略了)。它受到n^4的限制,但由于在许多情况下有充足的机会进行简化,可能会有比这更低的限制。但我不认为这种简化能够将其提高到n^2的水平。