写出不会运算超时的C语言代码 在一大堆数据中找出重复的是一件经常要做的事情。现在,我们要处理许多整数,在这些整数中,可能存在重复的数据。 你要写一个程序来做这件事情,读入数据,检查是否有重复的数据。如果有,输出“YES”这三个字母;如果没有,则输出“NO”。 输入格式: 你的程序首先会读到一个正整数n,n∈[1,100000],然后是n个整数。 输出格式: 如果这些整数中存在重复的,就输出:
时间: 2024-01-21 11:19:31 浏览: 27
以下是一个不会运算超时的C语言代码,使用哈希表来查找是否有重复数据:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100005
#define HASHSIZE 200003
typedef struct node {
int key;
struct node* next;
} Node;
Node* hashtable[HASHSIZE];
int hash(int key) {
return (key % HASHSIZE + HASHSIZE) % HASHSIZE;
}
Node* find(int key) {
int h = hash(key);
Node* p = hashtable[h];
while (p != NULL) {
if (p->key == key) return p;
p = p->next;
}
return NULL;
}
void insert(int key) {
int h = hash(key);
Node* p = (Node*)malloc(sizeof(Node));
p->key = key;
p->next = hashtable[h];
hashtable[h] = p;
}
int main() {
int n, x;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &x);
Node* p = find(x);
if (p != NULL) {
printf("YES\n");
return 0;
}
insert(x);
}
printf("NO\n");
return 0;
}
```
这个程序使用了哈希表来存储整数,并且使用链式哈希表来处理哈希冲突。对于每一个读入的整数,我们在哈希表中查找是否已经存在,如果已经存在,则说明有重复数据,输出"YES"并结束程序;否则,将这个整数插入到哈希表中,并继续读入下一个整数。如果遍历完所有整数后仍然没有找到重复数据,则输出"NO"。