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