题目
给定k个数组，每个数组有k个整数。每个数组中选取一个整数，一共k个整数，取其和，一共可以得到k^k个和。给出方法，求得这k^k个和中，最小的k个。
思路
（ 利用了堆，但是没有必要排序，所以时间复杂度较短，已用C++写出，请大家指正，谢谢 ）
（1）对K个数组进行建小堆（建堆复杂度为O(n)）；时间复杂度为 O（n*n）
（2）对k个数组都进行以下两步操作 时间复杂度 O（n * log n）
- first： 置换堆顶和最后一个元素O（1)
- second： 对堆进行维护操作 O(log n)
- first： 置换堆顶和最后一个元素O（1)
- second： 对堆进行维护操作 O(log n)
（3）对每个数组，以此拿堆顶和最后一个元素比较，得到差距最小的那个数和数组，可以得到第二小的和；然后这个数组的堆顶和倒数第二个数置换（倒 数最后一个为最小），堆规模减小，进行维护；时间复杂度为 O（n + log n）
（4）对第（3）步循环k-1次，得到最小的k个和，时间复杂度（n*(n + log n)）,即为 O（n*n）
综上：
总的时间复杂度为 O（n*n）
实验数据
原始数据
建堆后
这时候K个数的和最小的值出来了，即top-one（每个堆的堆顶元素之和）
接着置换操作，对每个堆把堆顶和最后一个元素置换，减小堆规模，对堆进行下溯维护操作，得出每个堆的第二小元素
然后求出每个数组里最小值和第二小值之差最小的那个数组，堆顶和倒数第二个数置换，堆规模减小，并进行维护操作，其他堆不动，这时候其实我们就可以找到k个数的和的t最小top-2，
第一次循环可以看出是第四个数组，差值最小（请你们注意我定义的D_value变量的含义，他保留的当前是之差最小的值）
然后重复上述操作k-1次
分别得出k个数的和的最小top-k个
（我表述能力欠缺，还请见谅）
结果 在下面
代码
test.cpp
// chen_1.cpp : Defines the entry point for the console application.
/*
question
给定k个数组，每个数组有k个整数。每个数组中选取一个整数，一
共k个整数，取其和，一共可以得到k^ k个和。给出方法，求得这k^ k个和中，最小的k个
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std ;
// Define a template class vector of int
typedef vector<int> IntVector ;
//Define an iterator for template class vector of strings
typedef IntVector::iterator IntVectorIt ;
const int VECTOR_SIZE = 10 ;
class heap
{
public:
void Data( IntVector * data,int SIZE )
{
for(int i=0;i<SIZE; i++ )
{
(data+i)->resize(SIZE);
for(IntVectorIt j = (data+i)->begin();j<(data+i)->end();j++)
{
*j = rand( ) % 100 ;
}
}
};
void Makeheap( IntVector * data,int SIZE )
{
for( int i=0;i<SIZE; i++ )
{
make_heap((data+i)->begin(), (data+i)->end(),greater<int>());
}
};
void ReCover(IntVector * data,int id,int s)
{
IntVectorIt p = (data+id)->begin() ;
//IntVectorIt e = (data+id)->end()-s ;
//int d ;
//int length = (e-p) ;
int i = 1 ;
while( 2*i <= s )
{
if( 2*i == s )
{
if( *(p+i-1) > *(p+i*2-1) )
{
cout<<id<<"------------------------------"<<endl;
this->swap(data+id,i-1,i*2-1);
i=i*2;
}
else
break;
}
else
{
cout<<"tree: "<<endl;
cout<<*(p+i*2-1)<<"\t"<<*(p+i*2+1-1)<<"\t"<<*(p+i-1)<<endl;
if( *(p+i*2-1) > *(p+i*2+1-1) )
{
if( *(p+i-1) > *(p+i*2+1-1) )
{
cout<<id<<"------------------------------"<<endl;
this->swap(data+id,i-1,i*2+1-1);
i=i*2+1;
}
else
break;
}
else
{
if( *(p+i-1) > *(p+i*2-1) )
{
cout<<id<<"------------------------------"<<endl;
this->swap(data+id,i-1,i*2-1);
i=i*2;
}
else
break;
}
}
}
};
void Show(IntVector * data,int SIZE)
{
cout<<"heap follows"<<endl;
for( int i=0;i<SIZE; i++ )
{
for( IntVectorIt j = (data+i)->begin() ;j<(data+i)->end() ;j++ )
{
cout<<*j<<"\t" ;
}
cout<<endl ;
}
cout<<endl ;
};
void Main(IntVector * data,int SIZE ,IntVector * result)
{
int repeat=1;
// data initilize
this->Data(data,SIZE);
this->Show( data,SIZE );
system("pause");
// make heap : running time O（n*n）
this->Makeheap(data,SIZE);
// cout heap : running time O（n*n）
cout<<repeat++<<endl;
this->Show( data,SIZE );
IntVectorIt k = result->begin();
cout<<"start"<<endl;
// set array id for the heaps length :running time( n )
int *id = new int[SIZE];
for(int i=0;i<SIZE;i++ )
{
*(id+i) = SIZE ;
}
// the min-top-1;running time( n * log n )
for( int i = 0 ;i< SIZE ; i++ )
{
(*k) = (*k) + (data+i)->front();
cout<<"----------------------------------------------------------------"<<i<<endl;
this->swap( (data+i), 0 , SIZE -1 );
this->ReCover( data,i ,SIZE -1 );
}
// cout heap
//cout<<repeat++<<endl;
this -> Show( data, SIZE );
cout<<*k<<endl;
// the min-top-(k-1) : runntime ( n * n )
int D_value;// = data->front() -data->back();
int flag ;//= 0;
for( k = result->begin()+1; k<result->end(); k++ )
{
*k = 0 ;
// cout heap
cout<<repeat++<<endl;
this -> Show( data, SIZE );
D_value = data->front() - *( data->begin() + *(id+0)-1 );
flag = 0;
for( int i=1 ;i< SIZE ; i++ )
{
if((data+i)->front()-(data+i)->back() < D_value )
{
D_value = (data+i)->front()-*( (data+i)->begin()+(SIZE-1) ) ;
flag = i ;
}
cout<<i<<" "<<(data+i)->front()<<" "<< *((data+i)->begin()+(*(id+i)-1) )<< " cout<<D_value:"<<D_value<<endl;
}
*(id+flag) =*(id+flag)-1;
cout<<"*(id+flag) "<<*(id+flag)<<endl;
this->swap( (data+flag), 0 , *(id+flag) -1 );
this->ReCover( data,flag ,*(id+flag)-1 );
*k = *(result->begin())+D_value ;
cout<<*k<<endl;
//system("pause");
}
for( k = result->begin(); k<result->end(); k++ )
{
cout<<"result: "<<*k<<"\t";
}
};
void swap(IntVector * data,int a,int b)
{
cout<<" swap "<<*(data->begin()+a)<<" "<<*(data->begin()+b)<<endl;
int d = *(data->begin()+a);
*(data->begin()+a)= *(data->begin()+b);
*(data->begin()+b) =d;
cout<<" swap later "<<*(data->begin()+a)<<" "<<*(data->begin()+b)<<endl;
};
};
int main( )
{
// 布置初始数据
//int data[VECTOR_SIZE][VECTOR_SIZE] ;
IntVector *Numbers = new IntVector[VECTOR_SIZE] ;
IntVector *data = new IntVector(VECTOR_SIZE);
heap * H = new heap();
// ask the min-k sum of the data:running time O（n * n）
H->Main( Numbers , VECTOR_SIZE ,data );
system("pause");
return 0 ;
}
好的，代码到此结束，谢谢大家观赏，我是第一次在网上写文章，写的不好之处还请大家严厉批评，我作为一个学生会好好改正学习的