Question

现有n个正整数，n≤100000，要求出这n个正整数中的第k个最小整数（相同大小的整数只计算一次），k≤400。

输入
第1行为n和k，第2行开始为n个正整数的值，整数间用空格隔开。

输出
第k个最小整数的值；若无解，则输出“NO RESULT”。
#include<stdio.h>
int main(void){
int a[101][101];
int b[101][101] = {0};
int n,k;
int i,j,l,c,d;
int count = 0;
scanf("%d%d",&n,&k);
for(i=0;i<100; i++)
for(j=1;j<=100;j++){
if(i*100+j<=n){
scanf("%d",&a[i][j]);
c=a[i][j]/100;
d=a[i][j]%100;
b[c][d]++;
}
else{
i=100;j=101;}
}
for(i=0;i<100; i++)
for(j=1;j<=100;j++){
if(b[i][j]!= 0){
count++;
l=i*100+j;
}
if(count == k){
i=100;j=101;}
}
if(count == k&&k<=400)
printf("%d\n",l);

else
printf("NO RESULT\n");
}
为什么运行错误

Answer 1

n≤100000和k≤400。

c=a[i][j]/100;

d=a[i][j]%100;

b[c][d]++;

这几行代码中 c就有可能是超过100的 比如输入的是100000。

这样c=1000。

b[c][d]就越界了。

只需要对每个输入的 进行插入排序，同时只保留前k个就好。

开一个400的数组。

最后a[k-1]就是结果。

含义

和整数一样，正整数也是一个可数的无限集合。在数论中，正整数，即1、2、3……；但在集合论和计算机科学中，自然数则通常是指非负整数，即正整数与0的集合，也可以说成是除了0以外的自然数就是正整数。正整数又可分为质数，1和合数。正整数可带正号（+），也可以不带。

Answer 2

题目只说 n≤100000和k≤400。

但是并没有限定输入整数的规模
这样
c=a[i][j]/100;
d=a[i][j]%100;
b[c][d]++;
这几行代码中 c就有可能是超过100的 比如输入的是100000
这样c=1000
明显 b[c][d]就越界了。

其实没那么复杂。
只需要对每个输入的 进行插入排序，同时只保留前k个就好。
开一个400的数组。
最后a[k-1]就是结果。

追问

谢谢你的建议，可我设成a[101][1001],为什么答案错误了

追答

算法本身就错了 出什么结果 都正常。

追问

我知道哪里错了

Answer 3

开一个int a[100000]的并初始化为0，依次输入i-N，把对应的a[i]改为1
然后从a[0]开始数为1的数，第K个就是第几个数为1的数，把i输出来
复杂度依次输入为N，一次循环N
N+N=N的复杂度