首页 > 代码库 > 寻找最小的整数

寻找最小的整数

题目:给定一个无序的整数数组,怎么找到第一个大于0,并且不在此数组的整数。比如[1,2,0]返回3,[3,4,-1,1]返回2,[1, 5, 3, 4, 2]返回6,[100, 3, 2, 1, 6,8, 5]返回4。要求使用O(1)空间和O(n)时间

解答:不停的让a[i] =i  归位。

#include <stdio.h>void Swap(int &a, int &b){  int c = a;  a = b;  b = c;}int FindFirstNumberNotExistenceInArray(int a[], int n){  int i;  for (i = 0; i < n; i++)    while (a[i] > 0 && a[i] <= n && a[i] != i + 1 && a[i] != a[a[i] - 1])        Swap(a[i], a[a[i] - 1]);  for (i = 0; i < n; i++)    if (a[i] != i + 1)      break;  return i + 1;}void PrintfArray(int a[], int n)  {    for (int i = 0; i < n; i++)      printf("%d ", a[i]);    putchar(\n);  } int main(){ const int MAXN = 5;  int a[MAXN] = {2, -100, 4, 1, 70};  PrintfArray(a, MAXN);  printf("该数组缺失的数字为%d\n", FindFirstNumberNotExistenceInArray(a, MAXN));  return 0;}

参考:http://blog.csdn.net/morewindows/article/details/12683723

寻找最小的整数