資源簡介
1.問題描述 設計算法實現在一個具有在n各互不相同元素的數組A[1…n]中找出所有前k個最小元素的問題,這里k不是常量,即它是輸入數據的一部分。要求算法的時間復雜性為Θ(n)。 2. 具體要求 輸入的第一行是一個正整數m,表示測試例個數。接下來幾行是m個測試例的數據,每個測試例的數據由三行組成,其中其中,第一行輸入一個正整數n,表示元素的個數;第二行輸入n個整數,整數之間用一個空格隔開。第三行輸入一個正整數k,表示求該組測試例中的前k個最小元素。(設給出的每個整數序列中的元素是唯一的。) 輸出:對于每個測試例輸出一行,由k個整數組成,表示輸入的n個整數中前k個最小元素。整數之間用一個空格隔開。
代碼片段和文件信息
#include
#define?M?100
#define?N?5
/*..利用快速排序將數組按升序排序..*/
int?partition?(int?key[]int?lowint?high)
{?
int?k;
k?=?key[low];
while(low? {
while(low=?k)?high--;
key[low]?=?key[high];
while(low key[high]?=?key[low];
}
key[low]?=?k;
return?low;
}
void?QSort(int?str[]int?lowint?high)
{
int?k;
if(low? {
??????k?=?partition(strlowhigh);
??QSort(strlowk-1);
??QSort(strk+1high);
}
}
/*...求中項...*/
void?mid(int?s[]int?i?int?r[])
{
int?j=5*i;
QSort(sjj+4);
r[i]=s[j+2];
}
/*...求數組的第K小元素...*/
int??select(int?A[]int?pint?k)
{
int?qi=0jst;
int?mc[M]small[M]mid1[M]big[M];
if(p<44)?
{
/*...直接排序...*/
QSort(A0p-1);
return?A[k-1];
}
/*...分成q組,每組5個元素...*/
q=p/5;
/*...求各組中項...*/
for(j=0;j {
mid(Ajc);
}
/*...遞歸調用求中項
- 上一篇:libiconv-1.9.2-lib
- 下一篇:linux下的串口調試助手
評論
共有 條評論