我正在寻找一种时间和空间复杂度最小的算法解决以下问题。
给定两个数组a和b,找到所有元素对(a1,b1),其中a1属于数组A,b1属于数组B,使得它们的和a1+b1=k(任意整数)。
我能想出一个O(n log n)的方法,其中我们将数组中的一个排序,比如A,对于数组B中的每个元素b,在已排序的数组A上执行二分查找以查找值(K-b)。
我们还能进一步改进吗?
如果数组最初未排序,则可以首先对它们进行排序,然后使用上述算法。有几种不同的排序方法可供选择,具体取决于您期望的数据类型:
平均来说,比较排序需要O(nlogn)的时间。后两种排序方法快于O(n log(n)),但如果输入数组中可能的值范围非常大,则可能不切实际。
a[i] + b[j] = k
,难道你不能同时更新两个指针吗?这不像是 a[i] + b[j-1] = k
,除非 b[j-1] = b[j]
,而在这种情况下,如果还有 a[i] = a[i+1]
,那么你应该输出什么呢?更具体地说,如果 a = [1, 1]
,b = [2, 2]
,k = 3
,那么你的输出长度应该为四吗?如果是这样,就要对所有相等值的运行进行运行长度编码,以保证不同的元素。虽然这增加了一些复杂性:现在你必须进行一些算术运算,才能确定原始数组中的索引,如果你想输出例如 [(0, 0), (0, 1), (1, 0), (1, 1)]
(在我的例子中)。 - Jonas Kölker如果您对最大可能数量有限制(命名为 M),则可以使用 O(M+n) 的解决方案。
使用布尔数组 false 并将 A 中的所有值标记为 true。然后对于 B 中的每个元素 b,检查元素编号 K-b 是否标记为 true。
如果使用哈希映射而不是大型数组,则可以进行改进。但在这种类型的问题中,我认为使用哈希映射有点作弊。
无论如何,插入的复杂度为 O(n),查询的复杂度为 O(n),总共是 O(n)。
编辑:
这可能是有用的一种情况:
使用我的想法(不是布尔而是整数(在每次运行时递增))会给您带来以下复杂度:
虽然使用的空间更多,但在这种情况下,您已将速度提高了 log(n) ~=20 倍!
k - a(n)
,如果查找成功,则生成一个输出元素。这将使用 O(n) 的空间和时间。var bSet = new HashSet(B);
var results = from a in A
let b = k - a
where bSet.Contains(b)
select new { a, b };
template< typename T >
std::vector< std::pair< T, T > >
find_pairs(
std::vector< T > const & a, std::vector< T > const & b, T const & k ) {
std::vector< std::pair< T, T > > matches;
std::sort( a.begin(), a.end() ); // O( A * lg A )
std::sort( b.begin(), b.end() ); // O( B * lg B )
typename std::vector< T >::const_iterator acit = a.begin();
typename std::vector< T >::const_reverse_iterator bcit = b.rbegin();
for( ; acit != a.end(); /* inside */ ) {
for( ; bcit != b.rend(); /* inside */ ) {
const T sum = *acit + *bcit;
if( sum == k ) {
matches.push_back( std::pair< T, T >( *acit, *bcit ) );
++acit;
++bcit;
}
else if( sum < k ) {
++acit;
}
else { // sum > k
++bcit;
}
}
} // O( A + B )
return matches;
}
我使用了C++,看起来它给了我想要的结果。希望这就是你在寻找的。
using namespace std;
using data=std::pair<int,int>;
void search_pairs(std::vector<int>& A, std::vector<int>& B, const int total, std::vector<data>& output){
std::sort(A.begin(),A.end(),[](const int i,const int j)->bool{return (i<j);});
std::sort(B.begin(),B.end(),[](const int a,const int b)->bool{return (a<b);});
std::vector<int>* minV(nullptr);
std::vector<int>* maxV(nullptr);
if(A.size()>B.size()) {minV=&B;maxV=&A;}
else {minV=&A;maxV=&B;}
for(auto&& itr:(*minV) ){
auto remain(total-itr);
if (std::binary_search (maxV->begin(), maxV->end(), remain)){
data d{itr,remain};
if (minV==&B) std::swap(d.first,d.second);
output.push_back(d);
}
}
if (minV==&B) std::reverse(output.begin(),output.end());
}
int main() {
size_t nb(0);
scanf("%lu",&nb);
for (size_t i=0;i<nb;++i){
size_t a,b(0);
int total(0);
scanf("%lu %lu %d",&a,&b,&total);
std::vector<int> A,B;
for (size_t i=0;i<a;++i){
int aux;
scanf("%d",&aux);
A.push_back(aux);
}
for (size_t i=0;i<b;++i){
int aux;
scanf("%d",&aux);
B.push_back(aux);
}
std::vector<data> output;
search_pairs(A, B, total, output);
auto itr=std::begin(output);
if (itr==std::end(output)) printf("-1");
while (itr!=std::end(output)){
printf("%d %d",(*itr).first, (*itr).second);
if (++itr!=std::end(output)) printf(", ");
}
printf("\n");
}
//code
return 0;
}
n
次的常数因子比对长度为n
的未排序数组进行排序要低,通常情况下。因此,您可能只想对一个数组(短数组)进行排序。 - Rex Kerra = {3, 3}
,b = {7, 7}
,且k = 10
,那么预期输出是什么? - Arun