数组中未出现的最小正整数（算法）

  1  #include <cstdio>
  2  #include <algorithm>
  3   using   namespace   std;
   4   int  s[ 100  ];
   5   int   main()
   6   {
   7       int   l,r;
   8       int   n;
   9       while (scanf( "  %d  " ,& n),n)
  10       {
  11           for ( int  i= 0 ;i<n;i++ )
  12              scanf( "  %d  " ,s+ i);
  13          l= 0  ;
  14          r= n;
  15           while (l< r)
  16           {
  17               if (s[l]==l+ 1  )
  18                  l++ ;
  19               else   if (s[l]<l+ 1 ||s[l]>r||s[s[l]- 1 ]== s[l])
  20                  s[l]=s[-- r];
  21                   else 
 22                  swap(s[l],s[s[l]- 1  ]);
  23           }
  24          printf( "  %d\n  " ,l+ 1  );
  25       }
  26       return   0  ;
  27  }

题目：

给定一个无序数组arr，找到数组中未出现的最小正整数。
要求：时间复杂度O(n),额外空间复杂度O(1);

变量的解释
l：表示从1-l已经存在的数
r：表示1-r想要得到的数

初始值：
l=0
r=n

走的过程

1>当l的位置值等于l+1，表示得到想要的
2>当l的位置值<l时，表示l位置的值已经存在，所以这个数组不会存在到r的值了 so r--
3>当l的位置值>r时，表示l的位置已经超过r，所以数组不会存在到r的值了， so r--
4>当l的位置值和l值的位置-1的的位置值相等时，所以数组不会存在到r的值了，so r--
5>当l的位置值>l&&<r&&l的位置值和l的位置-1位置不相等时，相互交换直到满足。

 

 

时间复杂度为nlog n的时间复杂度

  1  #include<cstdio>
  2  #include <algorithm>
  3   using   namespace   std;
   4   int   main()
   5   {
   6       int  s[ 100  ];
   7       int   n,c;
   8       while (scanf( "  %d  " ,& n),n)
   9       {
  10          c= 1  ;
  11           for ( int  i= 0 ;i<n;i++ )
  12              scanf( "  %d  " ,s+ i);
  13          sort(s,s+ n);
  14           for ( int  i= 0 ;i<n;i++ )
  15           {
  16               if (s[i]== c)
  17                  c++ ;
  18               else 
 19               {
  20                   if (s[i]> c)
  21                       break  ;
  22               }
  23           }
  24          printf( "  %d\n  "  ,c);
  25       }
  26       return   0  ;
  27  }

面试的题看起来简单，实则技巧性太强了。

查看更多关于数组中未出现的最小正整数（算法）的详细内容...