首页 > 试题广场 >

有A、B两个文件，文件格式相同，均为每行一个十进制整型数字，

[问答题]

有A、B两个文件，文件格式相同，均为每行一个十进制整型数字，两个文件的行数不一定相等，但均在一千万行左右。 A 文件中的数字两两不等， B 文件中的数字两两不等，请用一个算法找出 A 和 B 两文件中所有相同的数，并且从小到大有序输出。请考虑统计程序如何实现，给出设计思路和关键算法（可使用伪代码），并估计程序核心代码的时间复杂度和空间复杂度。

睡不醒的魔眼。

只能给你思路。用外部排序类似的算法。需要另外三个文件C、D和E，先从A中个读取一定数量的数字排序，排完序将这组数放在C文件中，同样操作，从B中读取相同量的数字排序放在D中，然后CD就是相当于外部排序的输入，AB相当于外部排序的输出，在外排过程中遇到相同的，就记录下来放在E中。

发表于 2015-11-25 16:50:20 回复(0)

牛客129174号

#define NODE_NUMBER 10000001
#define MOD 7
struct hash
{
int key;
struct hash * next;
hash() { next = NULL; }
} * ht[NODE_NUMBER];
int hash_insert(int k)
{
int key = k % MOD;
if (ht[key] == NULL) {
hash * tmp = new hash;
tmp->key = k;
ht[key] = tmp;
} else {
hash * tmp = ht[key];
int flag = 0;
while (tmp->next != NULL) {
if (tmp->key == k) {
flag = 1;
break;
}
tmp = tmp->next;
}
if (tmp->key == k) {
flag = 1;
}
if (flag == 0) {
hash * t = new hash;
t->key = k;
tmp->next = t;
}else {
return 1;
}
}
return 0;
}
int main()
{
int d[] = {100, 20, 21, 35, 3, 78, 99, 10};
int i;
memset(ht, 0, sizeof(ht));
for (i = 0; i < 8; ++i) {
printf("%d\n", hash_insert(d[i]));
}
for (i = 0; i < 7; ++i) {
hash * tmp = ht[i];
while (tmp != NULL) {
printf("%d ", tmp->key);
tmp = tmp->next;
}
printf("\n");
}
return 0;
}

发表于 2015-01-05 14:02:54 回复(1)