面试题算法之一

题目简单描述一下

有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);