Hash值的應(yīng)用
將存儲(chǔ)位置與數(shù)據(jù)本身對于起來的存儲(chǔ)手段
一鸵隧、例2.5 統(tǒng)計(jì)同成績學(xué)生人數(shù)
在已知該例可以用Hash的前提下 實(shí)現(xiàn)還是很簡單的 只怕實(shí)際做題時(shí)想不到該方法绸罗。。
需要注意的是：
初始化總是忘記要比用例數(shù)量多+1 如0~100的整數(shù)應(yīng)該是Hash[101]?
并且數(shù)組初始化為0是Hash[101]={0} 不是直接=0
二豆瘫、例2.6 Sort （按從小到大輸出前m大的數(shù)）
條件：待排序的數(shù)字?jǐn)?shù)量為1,000,000; 數(shù)據(jù)范圍為[-500,000,500,000]且各不相同;時(shí)間限制1s
分析：即使是快排珊蟀，復(fù)雜度O(nlogn)，也會(huì)達(dá)到千萬級外驱，超過1s系洛；
? ? ? ? ? 數(shù)據(jù)范圍有限俊性，考慮Hash，利用一個(gè)數(shù)組分別統(tǒng)計(jì)每一種數(shù)字是否出現(xiàn)描扯。
心得：這道題一開始真的沒想到怎么用Hash定页，但是一看到上面這句話就想通了（可怕！
? ? ? ? ? ?接下來再從尾到頭遍歷數(shù)組绽诚，時(shí)間復(fù)雜度在1,000,000百萬級
代碼出現(xiàn)的問題：
1）最開始定義a[1000001]={0}這個(gè)數(shù)字時(shí)典徊，放在了main函數(shù)里，導(dǎo)致運(yùn)行時(shí)棧溢出恩够。也就是說大數(shù)組應(yīng)該定義在main函數(shù)外卒落。
原因分析：
數(shù)組定義在函數(shù)中時(shí)，占用的內(nèi)存來自椃渫埃空間儡毕，棧空間是在進(jìn)程創(chuàng)建時(shí)初始化的扑媚，有固定的大小腰湾，一般為幾十KB，所以太大的數(shù)組會(huì)耗光椊桑空間费坊。而全局變量是在編譯的時(shí)候編到數(shù)據(jù)段的，可以比較大旬痹。
全局變量在靜態(tài)存儲(chǔ)區(qū)分配內(nèi)存附井，局部變量是在棧上分配內(nèi)存空間的。（c語言程序在運(yùn)行時(shí)會(huì)動(dòng)態(tài)創(chuàng)建一個(gè)堆棧段两残，里面存放著調(diào)用棧永毅，保存著函數(shù)的調(diào)用關(guān)系和局部變量。）如果數(shù)組太大人弓，可能會(huì)造成棧溢出卷雕。
所以對于大數(shù)組的定義，要么定義為全局變量票从，要么動(dòng)態(tài)分配內(nèi)存（malloc()來開辟堆空間漫雕，堆空間中的內(nèi)存是按需分配，自由增長的峰鄙，可以非常大浸间，32位的系統(tǒng)中可以大到4GB。）
2）該大數(shù)組雖然需要在外部定義吟榴，但是也需要在內(nèi)部初始化魁蒜，以免多組數(shù)據(jù)中用到已經(jīng)賦值的數(shù)組，影響結(jié)果。
3）輸出樣例中兜看，每個(gè)數(shù)字間隔了一個(gè)空格锥咸，但最后一個(gè)數(shù)字后無空格，所以應(yīng)該控制好空格的輸出
其他可改善的地方：
參考代碼中用到了OFFSET, 更有可讀性? #define OFFSET 500000
考慮題目中指明了數(shù)據(jù)“各不相同” 所以另外實(shí)現(xiàn)了數(shù)據(jù)相同時(shí)的Hash方法细移。其中主要的問題是空格的控制比較不熟練搏予。
