題目
給定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 ;
}
好的，代碼到此結束，謝謝大家觀賞，我是第一次在網上寫文章，寫的不好之處還請大家嚴厲批評，我作為一個學生會好好改正學習的