Question

为什么submit之后提示是Runtime Error:Segmentation fault？？ 我的代码和问题如下

#include<stdio.h>
int main()
{
int N,Q,i,j,flag,a[100],b[100];
scanf("%d%d",&N,&Q);
if (N==0&&Q==0)
return 0;
for (i=0;i<N;i++)
scanf("%d",&a[i]);
for (i=0;i<Q;i++)
scanf("%d",&b[i]);
for (i=0;i<Q;i++)
{
flag=0;
for (j=0;j<N;j++)
{
if (a[j]-b[i]==0)
flag=1;
}
if (flag==1)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}

Answer 1

scanf("%d%d",&N,&Q);
参数间有空格，输入格式里就也要加入，即scanf("%d %d",&N,&Q);

这里面，如果
1.输入的N个数没有重复数据
2.输入数据数值不超过int形范围，且大于等于0
3.存储用的数组的“体积”足够
就有个O(1)的查找方法。把数组的容量弄到最大，初始化为-1.然后把输入的数据i放到第i位。那么查找数据j就可以直接读第j位，结果如果相等，就是yes，反之就是no. 这就是最简单的hash table查找。

刚才仔细看了，居然是10万级别的存储，那么一维静态数组绝对不够用了！！！因为数组下标int的最大整数值是32767！！！

考虑open hashing：
1. 定义一个存储整数，并有一个指向下一个存储的数据结构
比如
struct node
｛
int content;
node* next
｝;
2. 定义一个node*的数组S[]，大小为10000
3. 每个数i的hash值用abs(i)%10000得到，这样负数也会有大于等于0的hash值
4. 把输入的数据i存储在S[abs(i)%10000]里
4.1 如果这里还没有存数据，直接分配存储给一个node，node的conten设为i，然后链接到这个位置
4.2 如果存有数据，在表头（即S[abs(i)%10000]这个位置）插入含有这个新的数据的node（在表头插入可以降低时间复杂度）
5. 查找数据j的时候，算j的hash值，就可以直接找到j对应的那个链表，在链表里再逐个找到j.
时间复杂度分析
1.建立表时每次插入的时间复杂度为O(1)
2. 查找的时候，找到表头为O(1)，一个表，由于整数范围为-32768 到32767，每个表长最多为7，还是可以视为O（1）级别的复杂度。

追问

你太厉害了！！！我现在只是初步，想参加ACM，请问前辈有什么建议吗？？

追答

看你是仅仅是为了参赛，还是为了学好编程本身。
在你已经弄懂基本的数据类型和控制结构后，短期提高的话可以这么来：
1. 首先弄清楚时间和空间复杂度什么意思，怎么算
2. 学会用C/C++手动写出单链表（这个是很多结构的基础，栈、堆、队列、树、图都可以链表实现）和相应的增删改查操作
3.然后，可以的话，学会用vector和deque这两个C++的模版类
4. 弄清楚基本的查找和排序算法，至少知道冒泡、块排和二分查找的思想。
你要是特别喜欢编程，那就从离散数学的图论部分和数理逻辑部分开始看，然后看java的书理解啥叫面向对象，后面看数据结构和算法的书（C语言或者C++,由于JAVA没有指针这个概念，学数据结构直接看java虽然好懂，但有时反而理解不透），最后再来看图形化应用开发、网络编程或者嵌入式系统之类的专门应用。

Answer 2

数组越界导致你的runtime error。
你的数组a,b声明的大小是100，而程序给的输入可能在100000数量级，导致数组越界问题。
for (i=0;i<N;i++)
scanf("%d",&a[i]); //这里
for (i=0;i<Q;i++)
scanf("%d",&b[i]); // 和这里
你修改a,b数组的大小为100001再试试吧。

追问

修改之后是time exceed..怎么办嗯？？

追答

10^6 * 10^6 =10^12次方应该会提示超时。
自己想锻炼的话，就自己写排序算法对a进行排序，二分查找。或者hash也可以。
另外一个想法，把输入存储成一个set(标准c++容器)，再试试。

Answer 3

你这算法就是一般的查找，时间复杂度太高是O(N*Q)，最大有10^10次方，肯定运行超时；先对a进行快速排序，再使用2分查找吧，应该能过

追问

可是提示的是数组越界啊

追答

确实是，越界也是一个问题。你看题目要求，系统N，Q最大是100000，你这都是100的肯定放不下；使用动态数组吧。然后用快排，2分查找

追问

果然还有 time exceed..谢谢侬！！请问想参加ACM的我现在刚刚起步，你能推荐什么比较好的书籍吗？？

追答

数据结构先看完，再看看算法导论，清华的那个算法设计；代码多练习