哈希排序算法

說明

哈希算法是一種以空間換取時(shí)間的算法。

下面以一個(gè)例題的方式來進(jìn)一步說明這個(gè)算法。

• 時(shí)間復(fù)雜度 O(n)

例題

問題描述

HDU 1425 “Sort”給你n個(gè)整數(shù)，請按從大到小的順序輸出其中前m大的數(shù)。輸入：每組數(shù)據(jù)有兩行，第一行有兩個(gè)數(shù)n和m(0<n,m<1000000)，第2行包含n個(gè)各不相同，且都處于區(qū)間[-500000,500000]的整數(shù)輸出：對每組測試數(shù)據(jù)從大到小的順序排列并輸出前m大的數(shù)輸入樣例： 5 3 3 -35 92 213 -644輸出樣例： 213 92 3

問題分析

對于本問題有以下信息

• 區(qū)間長度為1000001
• 從大到小輸出
• 只輸出m個(gè)
• 沒有相同的數(shù)

在沒有相同的數(shù)的情況下，我們很顯然可以用哈希算法排序，且這個(gè)數(shù)組的大小為1000001。

具體思路就是，在輸入數(shù)字t的時(shí)候，在數(shù)組a[500000+t]處標(biāo)記為1，然后從數(shù)組最后開始向前檢索，即a[i]處為1則輸出500000-i,并依次打印m個(gè)這個(gè)數(shù)

題解

#include <bits/stdc++.h>using namespace std;//數(shù)組大小 #define MAXSIZE 1000001//因?yàn)槿植糠轴尫旁诙阎?#xff0c;所以數(shù)組寫這里可以開得更大 int a[MAXSIZE];int main() {int n,m;//因?yàn)楸绢}數(shù)據(jù)較大，所以用ci比較慢改用scanfwhile(~scanf("%d%d",&n,&m)){//將數(shù)組全部置為0以方便后面標(biāo)記a[i]memset(a,0,sizeof(a));for(int i=0; i<n; i++){int t;scanf("%d",&t);//關(guān)鍵步驟a[500000+t] = 1; //數(shù)字t,標(biāo)記在這個(gè)位置，這樣相當(dāng)于在存放的時(shí)候就已經(jīng)排好序了}//開始從后往前檢索m個(gè)數(shù)for(int i=MAXSIZE-1; m>0; --i){//若該處有標(biāo)記if(a[i]){if(m>1)printf("%d ", i-500000);elseprintf("%d\n", i-500000); //最后一個(gè)數(shù)要換行單獨(dú)處理--m; //因?yàn)橐敵鰉個(gè)數(shù)，所以每輸出一次，m依次自減1}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的哈希排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。