给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。 思路：设置一个Lb作为标志顺序表，遍历La，如果La中出现一个正整数，则令Lb.elem[La.elem[i]] = 1, 证明La中曾经出现过这个正整数
#include<stdio.h> #include<stdlib.h> #define LISTINITSIZE 10 typedef struct { int *elem; int length; int listsize; }sqlist; bool initlist_sq(sqlist &L); int main() { sqlist La,Lb; initlist_sq(La); initlist_sq(Lb);//定义顺序表 int i; printf("请输入顺序表La的长度："); scanf("%d", &La.length); Lb.length = La.length + 1; printf("请输入顺序表La中的元素："); for(i = 0; i < La.length; i ++) scanf("%d", &La.elem[i]); for(i = 1; i <= Lb.length; i ++) Lb.elem[i] = 0; //将顺序表Lb清零 for(i = 0; i < La.length; i ++) if(La.elem[i] >= 1) Lb.elem[La.elem[i]] = 1;//设置一个Lb作为标志顺序表，如果La中出现一个正整数，则令Lb.elem[La.elem[i]] = 1 for(i = 1; i <= Lb.length; i ++) if(Lb.elem[i] == 0) break;//最早出现的LB为零的元素，即为未出现的最小正整数 printf("线性表中未出现的最小正整数是：%d\n", i); } bool initlist_sq(sqlist &L)//初始化顺序表 { L.elem = (int *)malloc(LISTINITSIZE *sizeof(int)); if(!L.elem) return false; L.length = 0; L.listsize = LISTINITSIZE; return true; }