寻找一个数组中未出现的最小正整数(数组元素可重复)

题目描述

Description

Given nn non-negative integers, please find the least non-negative integer that doesn’t occur in the nn numbers.

Input

The first line is an integer T, representing the number of test cases.(T≤10)
The first line of each test case is an integer n (n≤2∗10​^5​​).
The second line of each test case are nn non-negative integers ai​​ (ai​​<2​^31​​).

Output

For each test case, output a line with the answer.

输入样例

2

4

4 0 1 3

2

1 1

输出样例

2

0

 

分析:暴力数字范围给定,暴力搜索其实也不是不可以,但是肯定会超时,网上有很多解法针对的都是数组元素不重复的情况,参考价值也不是很大,后来我自己想了一种方法,需要先进行排序,之后从头遍历,需要记录下来重复数字的重复次数,根据数组下标和重复次数之间的 关系,得到解答。时间复杂度O(n),空间复杂度O(1)

寻找一个数组中未出现的最小正整数(数组元素可重复)

代码:

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<string>
 4 #include<vector>
 5 using namespace std;
 6 int main()
 7 {
 8     int n;
 9     cin >> n;
10     // 打比赛时使用GCC编译器,务必要将两个>之间打上空格,以免误判
11     vector<vector<int> > v(1001,vector<int>(200001,INT_MAX));
12     vector<int> len(1001);
13     for (int i = 0; i < n; i++)
14     {
15         //int m;
16         cin >> len[i];
17         for (int j = 0; j < len[i]; j++)
18             cin >> v[i][j];
19     }
20     for (int i = 0; i < n; i++)
21     {
22         int res = 0;
23         int repNum = 0;
24         sort(v[i].begin(), v[i].end());
25         if (v[i][0] > 0)
26         {
27             cout << 0 << endl;
28             continue;
29         }
30         else
31         {
32             int j = 1;
33             for ( ; j < len[i]; j++)
34             {
35                 if (v[i][j] == v[i][j - 1])
36                 {
37                     repNum++;
38                     continue;
39                 }
40                 if (v[i][j] != j - repNum)
41                 {
42                     cout << j - repNum << endl;
43                     break;
44                 }
45             }
46             if (j == len[i])
47                 cout << len[i] << endl;
48         }
49     }
50     system("pause");
51     return 0;