散列

散列簡(jiǎn)單來(lái)說：給N個(gè)正整數(shù)和M個(gè)負(fù)整數(shù)，問這M個(gè)數(shù)中的每個(gè)數(shù)是否在N中出現(xiàn)過。

比如：N：{1,2,3,4}，M{2,5,7}，其中M的2在N中出現(xiàn)過
對(duì)這個(gè)問題最直觀的思路是：對(duì)M中每個(gè)欲查的值x，都在N中遍歷一次，時(shí)間復(fù)雜度為 O(NM),但當(dāng)N和M的值很大時(shí)，顯然無(wú)法承受

所以，我們可以設(shè)定一個(gè)bool型數(shù)據(jù) hashTable[100010],其中hashTable[x]== true 表示正整數(shù)x在N個(gè)正整數(shù)中出現(xiàn)過，而hashTable[x]= false表示正整數(shù)x在N個(gè)正整數(shù)中沒有出現(xiàn)過。這樣就可以在一開始讀入N個(gè)正整數(shù)時(shí)就進(jìn)行預(yù)處理，即當(dāng)讀入的數(shù)為x時(shí)，就令hashTable[x] = true （說明: hashTable 數(shù)組需要初始化為false,表示初始狀態(tài)下所有數(shù)都未出現(xiàn)過)。 于是，對(duì)M個(gè)欲查詢的數(shù)，就能直接通過hashTable數(shù)組判斷出每個(gè)數(shù)是否出現(xiàn)過。顯然這種做法的時(shí)間復(fù)雜度為O(N+M)，代碼如下:

#include<cstdio> const int maxn=1; //見注1 //maxn的值可以取大于0的任意數(shù) bool hashTable[maxn]={false}; //見注2 int main() {int n,m,x;printf("輸入n m的值\n"); scanf("%d%d",&n,&m); //輸入nm兩個(gè)數(shù)組各自的長(zhǎng)度for(int i=0;i<n;i++){printf("輸入第一組參照的第%d個(gè)x的值\n",i+1); scanf("%d",&x); //鍵盤輸入n的數(shù)據(jù)hashTable[x]=true; }for(int i=0;i<m;i++){ printf("輸入第二組的第%d個(gè)值\n",i+1); scanf("%d",&x); //鍵盤輸入m的數(shù)據(jù)if(hashTable[x]==true) //判斷數(shù)據(jù)相同{printf("yes\n"); //相同則返回yes，否則返回no}elseprintf("no\n");} }

注1：/* const 允許指定一個(gè)語(yǔ)義約束，編譯器會(huì)強(qiáng)制實(shí)
施這個(gè)約束，允許程序員告訴編譯器某值是保持不變的。如果在編程中確實(shí)有某個(gè)值保持不變，
就應(yīng)該明確使用const，這樣可以獲得編譯器的幫助。 即const是使這個(gè)值固定不再改變*/

注2：bool類型 為邏輯型，它的值只有true（1）和false（0）兩種值。
空間換時(shí)間，定義一個(gè)bool型數(shù)組hashTable[100010],其中hashTable[x]==true表示正整數(shù)x在N個(gè)正整數(shù)中出現(xiàn)過。這樣就可以在一開始讀入N個(gè)正整數(shù)的時(shí)候就進(jìn)行預(yù)處理。
同樣的，如果題目要求M個(gè)欲查詢的數(shù)中每個(gè)數(shù)在N個(gè)數(shù)中出現(xiàn)的次數(shù)，那么可以把nastTable數(shù)組替換為int型，然后在輸入N個(gè)數(shù)時(shí)進(jìn)行預(yù)處理，即當(dāng)輸入的數(shù)為x時(shí)，就令nhashTable[x]++,這樣就可以用O(N + M)的時(shí)間復(fù)雜度輸出每個(gè)欲查詢的數(shù)出現(xiàn)的次數(shù)。代碼如下:

#include<cstdio> const int maxn=1; /* const 允許指定一個(gè)語(yǔ)義約束，編譯器會(huì)強(qiáng)制實(shí) 施這個(gè)約束，允許程序員告訴編譯器某值是保持不變的。如果在編程中確實(shí)有某個(gè)值保持不變， 就應(yīng)該明確使用const，這樣可以獲得編譯器的幫助。*/ bool hashTable[maxn]={false}; int main() {int n,m,x;printf("輸入n m的值\n"); scanf("%d%d",&n,&m);for(int i=0;i<n;i++){printf("輸入第一組參照的第%d個(gè)x的值\n",i+1); scanf("%d",&x);hashTable[x]=true; }for(int i=0;i<m;i++){ printf("輸入第二組的第%d個(gè)值\n",i+1); scanf("%d",&x);if(hashTable[x]==true){printf("yes\n");}elseprintf("no\n");} }

總結(jié)

以上是生活随笔為你收集整理的散列的使用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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