[導(dǎo)讀]導(dǎo)引問題
Problem Description
給你n個整數(shù)，請按從大到小的順序輸出其中前m大的數(shù)。
Input
每組測試數(shù)據(jù)有兩行，第一行有兩個數(shù)n,m (0
導(dǎo)引問題
Problem Description
給你n個整數(shù)，請按從大到小的順序輸出其中前m大的數(shù)。
Input
每組測試數(shù)據(jù)有兩行，第一行有兩個數(shù)n,m (0
思考： 常規(guī)算法的缺陷？ 常規(guī)算法需要先對輸入的值進行存儲，然后進行排序，最后再進行輸出前m個數(shù)，n的數(shù)值很大是，對整體排序的時間會很長。
是否可以將“數(shù)據(jù)值”和“存儲位置”做某種對應(yīng)？ 因為數(shù)據(jù)的范圍有限制的，數(shù)據(jù)量的多少也是有限制的，所以必然可以想辦法讓大的數(shù)據(jù)對應(yīng)大的存儲位置，小的數(shù)據(jù)對應(yīng)小的存儲位置。--優(yōu)點，存儲完畢，排序完畢，省去了排序的時間，缺點，對應(yīng)關(guān)系找的不好的話，對空間的要求估計會比原來大很多。
哈希表 基本原理 哈希表（散列表）的基本原理： 使用一個下標范圍比較大的數(shù)組來存儲元素，一般通過設(shè)計一個函數(shù)（哈希函數(shù)，即散列函數(shù)），使得每個元素的關(guān)鍵字都與一個函數(shù)值（即數(shù)組下標）相對應(yīng)，然后用該數(shù)組單元來存儲對應(yīng)元素。
函數(shù)構(gòu)造 最常見的方法：除余法?H(k ) = k mod p (p一般選取適當大的素數(shù))
沖突 由于不能夠保證每個元素的關(guān)鍵字與函數(shù)值是一一對應(yīng)的，因此很有可能出現(xiàn)如下情況：“對于不同的元素關(guān)鍵字，Hash函數(shù)計算出了相同的函數(shù)值”，這就是產(chǎn)生了所謂的“沖突”。換句話說，就是Hash函數(shù)把不同的元素分在了相同的下標單元。 沖突解決 常用方法：線性探測再散列技術(shù) 即：當 h(k)位置已經(jīng)存儲有元素的時候，依次探查 (h(k)+i) mod S, i=1,2,3…，直到找到空的存儲單元為止。其中， S為數(shù)組長度。 特別地，如果將數(shù)組掃描一圈仍未發(fā)現(xiàn)空單元，則說明哈希表已滿，這會帶來麻煩，但是，該情況完全可以通過擴大數(shù)組范圍來避免。 基本操作 Hash表初始化（0或-1或其它） 哈希函數(shù)運算 插入元素（包含沖突解決） 定位（需考慮可能沖突的情況） 優(yōu)缺點總結(jié) Hash函數(shù)評價標準： 低沖突率 易于編碼 Hash函數(shù)特點： 優(yōu)點：數(shù)據(jù)存儲和查找效率高 （幾乎是常數(shù)時間） 缺點：消耗較多內(nèi)存（內(nèi)存很便宜哪～） Hash主要應(yīng)用： 查找元素是否屬于集合 搜索中的狀態(tài)表示
Hash的應(yīng)用 n給定一個包含N(N<=3000)個正整數(shù)的序列，每個數(shù)不超過5000，對它們兩兩相加得到的N*(N-1)/2個和，求出其中前M大的數(shù)(M<=1000)并按從大到小的順序排列。 n?Input n輸入可能包含多組數(shù)據(jù)，其中每組數(shù)據(jù)包括兩行： n第一行兩個數(shù)N和M， n第二行N個數(shù)，表示該序列。 n? nOutput n對于輸入的每組數(shù)據(jù)，輸出M個數(shù)，表示結(jié)果。輸出應(yīng)當按照從大到小的順序排列。
思考： 常規(guī)算法的缺陷？ 常規(guī)算法需要先對輸入的值進行存儲，然后進行排序，最后再進行輸出前m個數(shù)，n的數(shù)值很大是，對整體排序的時間會很長。
是否可以將“數(shù)據(jù)值”和“存儲位置”做某種對應(yīng)？ 因為數(shù)據(jù)的范圍有限制的，數(shù)據(jù)量的多少也是有限制的，所以必然可以想辦法讓大的數(shù)據(jù)對應(yīng)大的存儲位置，小的數(shù)據(jù)對應(yīng)小的存儲位置。--優(yōu)點，存儲完畢，排序完畢，省去了排序的時間，缺點，對應(yīng)關(guān)系找的不好的話，對空間的要求估計會比原來大很多。
哈希表 基本原理 哈希表（散列表）的基本原理： 使用一個下標范圍比較大的數(shù)組來存儲元素，一般通過設(shè)計一個函數(shù)（哈希函數(shù)，即散列函數(shù)），使得每個元素的關(guān)鍵字都與一個函數(shù)值（即數(shù)組下標）相對應(yīng)，然后用該數(shù)組單元來存儲對應(yīng)元素。
函數(shù)構(gòu)造 最常見的方法：除余法?H(k ) = k mod p (p一般選取適當大的素數(shù))
沖突 由于不能夠保證每個元素的關(guān)鍵字與函數(shù)值是一一對應(yīng)的，因此很有可能出現(xiàn)如下情況：“對于不同的元素關(guān)鍵字，Hash函數(shù)計算出了相同的函數(shù)值”，這就是產(chǎn)生了所謂的“沖突”。換句話說，就是Hash函數(shù)把不同的元素分在了相同的下標單元。 沖突解決 常用方法：線性探測再散列技術(shù) 即：當 h(k)位置已經(jīng)存儲有元素的時候，依次探查 (h(k)+i) mod S, i=1,2,3…，直到找到空的存儲單元為止。其中， S為數(shù)組長度。 特別地，如果將數(shù)組掃描一圈仍未發(fā)現(xiàn)空單元，則說明哈希表已滿，這會帶來麻煩，但是，該情況完全可以通過擴大數(shù)組范圍來避免。 基本操作 Hash表初始化（0或-1或其它） 哈希函數(shù)運算 插入元素（包含沖突解決） 定位（需考慮可能沖突的情況） 優(yōu)缺點總結(jié) Hash函數(shù)評價標準： 低沖突率 易于編碼 Hash函數(shù)特點： 優(yōu)點：數(shù)據(jù)存儲和查找效率高 （幾乎是常數(shù)時間） 缺點：消耗較多內(nèi)存（內(nèi)存很便宜哪～） Hash主要應(yīng)用： 查找元素是否屬于集合 搜索中的狀態(tài)表示
Hash的應(yīng)用 n給定一個包含N(N<=3000)個正整數(shù)的序列，每個數(shù)不超過5000，對它們兩兩相加得到的N*(N-1)/2個和，求出其中前M大的數(shù)(M<=1000)并按從大到小的順序排列。 n?Input n輸入可能包含多組數(shù)據(jù)，其中每組數(shù)據(jù)包括兩行： n第一行兩個數(shù)N和M， n第二行N個數(shù)，表示該序列。 n? nOutput n對于輸入的每組數(shù)據(jù)，輸出M個數(shù)，表示結(jié)果。輸出應(yīng)當按照從大到小的順序排列。
#include
#define MAX1 3000*2999/2+10//N最大取3000，最多有3000*2999/2個數(shù),擴大了5倍
#define MAX2 3000
int mask[MAX1]={0};
/**因為處理不好哈希沖突，經(jīng)常出現(xiàn)小的數(shù)被存儲在大的數(shù)據(jù)后面，和原來的大的存在高地址，小數(shù)
存儲在低地址相違背了。因為原來的規(guī)則是存在k%MAX1的位置，如果位置有的話，就繼續(xù)向后找，但是很可能出現(xiàn)后面
已經(jīng)存儲了比較大的數(shù)，所以處理不好，即使把k和k+1的間隔擴大幾倍也很可能出現(xiàn)。就是k存儲在k*10%MAX位置，
也有可能出錯，所以設(shè)置了掩碼位，計算相同的數(shù)個數(shù)*/
int h1[MAX1]={0};
int h2[MAX2]={0};//存儲用的
int main()
{
int M,N,count=0;
int i,j,k,t,s=0;
while(scanf("%d %d",&N,&M)!=EOF)
{
memset(h1,0,MAX1);
memset(h2,0,MAX2);
memset(mask,0,MAX1);
for(i=0;i=0;t--)
{
while(mask[t])
{
mask[t]--;
printf("%d ",h1[t]);
count++;
}
if(count==M)
{
printf("n");
break;
}
}
}
return 0;
} 
下載文檔
