题目描述

《重复的数》

【重复的数】数值哈希 给定 N 个自然数 ni (0<=ni<=10^9)。如果其中存在重复的数，则输出“yes”，否则输出“no”。重复的数是指一个数出现 1 次以上。(N<=10000) 【输入样例1】 5 1 2 3 1 4 【输出样例1】 yes 【输入样例2】 5 10023 20003 30334 12323 43333 【输出样例2】 no 【输入样例3】 6 1967 10023 20003 30334 10023 43333 【输出样例3】 yes #include #include using namespace std; const int P = 10007; // 一个质数 // 哈希函数 int hashID(int key){ return key % P; } // 哈希表（存储结构） ：一个向量数组 vector table[P+2]; // 表的尺寸要比P大 int main() { int N,ni; cin >> N; for(int i=1;i<=N;i++){ cin >> ni; int index = hashID(ni);// 计算哈希地址（数组下标） // 先查看这个地址下的动态数组中，ni是否已经存在，是，则说明出现重复的数 for(int j=0;j< table[index].size();j++){ if(table[index][j] == ni){ cout << "yes" << endl; return 0; } } table[index].push_back(ni); // 不重复的，添加到向量中 } // 所有数都不重复 cout << "no" << endl; return 0; }

输入格式

无

输出格式

（见样例）

样例

输入样例 1

5
1 2 3 1 4

输出样例 1

yes

输入样例 2

5
10023 20003 30334 12323 43333

输出样例 2

no

输入样例 3

6
1967 10023 20003 30334 10023 43333

输出样例 3

yes