首页 > 代码库 > 寻找最小的整数
寻找最小的整数
题目:给定一个无序的整数数组,怎么找到第一个大于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
寻找最小的整数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。