博客

问题描述：

给定N个正整数，给定M个正整数。如N = {7，8，2，4}，M = {8，2}，查找集合M中的正整数是否在集合N出现过。

暴力枚举：

#include<cstdio>

int main(){
    int arr[N] = {7,8,2,4};
    int brr[M] = {8,2};
    for(int i=0;i < N;++i){
        if(int j=0;j < M;++i){
            if(arr[i] == brr[j]){
                printf("brr[%d] == arr[%d]\n",j,i);
            }
        }
    }
}

这样的算法时间复杂度O(M*N)，显然随着问题规模度的增加，这样的算法是给糟糕的，难以接受的。

而hash提供的思路是

用空间换时间

，设定一个bool的hashtable数组，以hashtable[x] = true表示数据x在集合N出现过。而对于处理M个欲查询的数字是否在N出现，时间复杂度O(M+N)，改善为线性阶的时间复杂度。而对于现代计算机来讲，存储空间已经不是制约算法性能的因素了，因此采用用空间换时间的策略是完全行得通的，甚至是优秀的。

//hash.c
#include<cstdio>
#define bool int
#define false 0
#define true 1
const int MAX = 10000;
bool HashTable[MAX] = {false};
int main(){
    int arr[] = {7,8,2,4};
    int N = sizeof(arr)/sizeof(arr[0]);
    int brr[] = {8,2};
    int M = sizeof(brr)/sizeof(brr[0]);
    for(int i=0;i < M:++i){
        HashTable[arr[i]] = true;
    }
    for(int j=0;j < N;++j){
        if(HashTable[brr[j]] == true){
            printf("%d 出现过!\n",brr[j]);
        }
    }
    return 0;
}

对于字符串问题的处理，hash这样的处理方式往往是利器！