题目简单描述一下
有0，1，2，3，…，n-1将他们乱序放入一个数组，请排序。
首先是提问：
- 没有重复？没有
- 没有负数？没有
- 数组的长度就是n？是的
- n值很大吗？正常。
- 对于实现的算法有没有时间复杂度和空间复杂度的要求？O(n),O(1)
想一想数值与下标的关系：
- 数值与下标是一样的！
那么事情就好办了，此处选用C语言来完成这个题目。
分析：
暴力解决。
直接赋值a[i]=i最终要实现的结果就是下标==所对应的数字。
设数组为a[N] = {2,4,1,3,0,…};
目标数组为{0,1,2,3,4,…};
a[0]=2,目标 a[2]=2 ，即 a[a[0]]=2,
a[1]=4,目标 a[4]=4 ，即 a[a[1]]=4,
a[2]=1,目标 a[1]=1 ，即 a[a[2]]=1,
a[3]=3,目标 a[3]=3 ，即 a[a[3]]=3,
a[4]=0,目标 a[0]=0 ，即 a[a[4]]=0,
…
a[n]=m,目标 a[m]=m，即 a[a[n]]=m.
其实就是将a[i]放到a[a[i]]中去；实现的方法很简单
遍历数组，当下标等于值的时候i++；不等的时候将a[i] 和 a[a[i]]交换即可。利用一重for循环就可以了。
int i=0;
while(i!=n){
if(a[i]==i){
i++;
}else{
swap(a[i],a[a[i]]);
}
}
紧接着第二问
现在该数组中存储的数值什么都有，负数也有正数也有，0也有，但依旧没有重复值，那么请找出这里面最小的没出现的正整数。
信息整理
- 整数+0
- 最小的没出现的正整数
- 对于实现的算法有没有时间复杂度和空间复杂度的要求? O(n),O(1)
思考
- 这道题和前面那道题有关吗？
应该是有关的。想一想也确实有关。 - 我要怎么得到正整数？
如果我不处理那些负数，和第一道题一样，使得下标对应的数值和下标相等。这样我的数组里面就会出现一部分下标=下标对应的数值，一部分下标对应的是负数。 - 最小的没出现的正整数怎么得到？
直接遍历数组从 i=1 开始，当a[i]!=i的时候i的数值就是要求的。
真的是这样吗？
- 先来一批测试用例：
{0,1,2,3,4,5,6}=>7
{0,1,2,3,4,5,7}=>6
{-1,-2,-3,-4,-5,-6,0}=>1
{-1,1,2,3,5,6,7}=>4
{7,1,2,3,4,5,6}=>8 ——>** 特别小心** !
- 分析测试用例
遍历数组，从 i=1 开始，因为0不是正整数，可跳过。
i=1 a[1]!=1，此时应该输出1，就是 i；
1<i<n a[i]!=i，此时应该输出 i ；
i=n 分为如下两种情况：
A. a[n-1] +1 != a[0],输出 i；
B. a[n-1] +1 == a[0],输出a[0]+1；
实现
int result,i=0;
while(i!=n){
if(a[i]==i||a[i]<0||a[i]>=n){
i++;
}else{
swap(a[i],a[a[i]]);
}
}
for(i=0;a[i]==i&&i<n;i++);
result=i;
if(i==n&&a[n-1]==a[0]-1){
result = a[0]+1;
}
printf("%d",result);
