缺失的正整数
问题描述:
有一个没有排序过的整型数组,你需要找到其中缺失的第k个正整数。
要求:时间复杂度O(n),空间为O(1)。
输入包含多行的测试数据,每个测试数据占1行。
第一行输入n为测试数据的个数
接下来每个测试数据占3行。
第一行有一个数字,为数组中数据的个数m。
第二行有m个数,为数组中的数,这一行的每个数之间以空格为间隔。
第三行有一个数字,为k。
每组测试数据之间有一个空行作为间隔。
对于每组测试数据,输出一个整数,为该组数据缺失的第k个正整数。
每组测试数据的结果结尾为换行符。
对于100%的数据,0 < m < 10^9, a(a是数组中的任何可能的数) < 10^4,
0 < k < 10^8。
Sample input:
3
3
1 2 0
1
4
3 4 -1 1
1
5
7 8 9 11 12
2
Sample output:
3
2
2
数据说明:
对于100%的数据,0 < m < 10^9, a(a是数组中的任何可能的数) < 10^4,
0 < k < 10^8。
信息
- ID
- 1298
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者