携程旅行网 :查找最小缺失数
发布于 2017-09-21 19:51 3396 次浏览 0 赞 来自 我要提问  

携程旅行网 2018校招 研发类在线考试

编程题|20.0分3/3

查找最小缺失数

时间限制:C/C++语言 1000MS;其他语言 3000MS
内存限制:C/C++语言 65536KB;其他语言 589824KB

题目描述:

输入为一个无序数组,输出数组中不存在的最小正整数。

输入

第一行为数组大小n

接下来n行为数组元素

样例输入

5

3

4

-1

1

6


样例输出

2


9 条回复

排序一下就出来了吧

2017-09-21 20:06

leetcode 41 但是用了一段过了leetcode的代码无法全部AC 80% 是什么奇怪的测试用例?也没想通

2017-09-21 20:26

这题数据绝逼的有问题,怎么写都是80%。哪个全过了的?跪求打脸

2017-09-21 20:40

装桶AC了

2017-09-21 21:02
coder_EERKZNRJ 回复 acmcoderQXxTh5ka

桶开了多大?有特殊数据吗?

2017-09-21 21:11

我的全过了

代码:

#include <iostream>

#include <vector>

#include <numeric>

#include <limits>


using namespace std;



/*请完成下面这个函数,实现题目要求的功能

当然,你也可以不按照下面这个模板来作答,完全按照自己的想法来 ^-^

******************************开始写代码******************************/

int findMinMis(vector < int > A) {

for (int i = 0; i < A.size() - 1; i++)

{

for (int j = A.size() - 1; j > i; j--)

{

if (A[j] < A[j - 1])

swap(A[j], A[j - 1]);

}

}

for (int i = 0; i < A.size();)

{

while (A[i] <= 0)

{

i++;

}

if (A[i] != 1)

return 1;

else

{

int j = 2;

while (A[i] == A[i + 1] - 1)

{

i++;

j++;

}

return j;

}


}


}

/******************************结束写代码******************************/



int main() {

int res;


int _A_size = 0;

cin >> _A_size;

cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

vector<int> _A;

int _A_item;

for (int _A_i = 0; _A_i<_A_size; _A_i++) {

cin >> _A_item;

cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

_A.push_back(_A_item);

}




res = findMinMis(_A);

cout << res << endl;


return 0;


}


2017-09-21 22:36
1

import java.util.Scanner;


public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int a;

int num=0;

int n=sc.nextInt();

int []a1=new int[n];

for(int i=0;i<n;i++)

a1[i]=sc.nextInt();

for(int i=0;i<n;i++)

{

if(a1[i]<0)

continue;

num++;

}

int []a2=new int[num];

for(int i=0;i<n;i++)

{

if(a1[i]<0)

continue;

if(a1[i]>num-1)

continue;

else

a2[a1[i]]=1;

}

for(int i=0;i<num;i++)

if(a2[i]==0)

System.out.println(i);


}

}


2017-09-21 23:07
coder_RTZZDGK8 回复 coder_EERKZNRJ

有没有考虑过 -3 -2 -1,或者 2 3 4 这种数据?

2017-09-21 23:36
coder_EERKZNRJ 回复 coder_RTZZDGK8

我,,我直接把负数去掉然后排序,扫一遍,80%。然后换个方法。负数去掉用桶排,80%.你给的这两组数据我绝对能过的

2017-09-26 21:15
添加回复
回到顶部