第二种方法就是给数组排序，使用快速排序的时间复杂度是O(nlogn), 排血之后所有的负数都可以pass掉了。从正数开始，设置两个记录，记录当前正数和当前正数的前一个正数，再对这两个数进行比较，如果前一个正数+1等于当前正数，那么继续遍历数组，如果不等于，那么我们要找的数就是当前正数的前一个数+1。这就是我们丢失的最小正数。同时还要考虑特殊的情况，就是所有数值都是0或者所有数值都是负数的情况，这些直接都返回1就好了。排序的时间复杂度是O(nlogn)加上查找时间O(n)。下面给出详细代码：
[cpp]
#include
int partition(int *a, int low, int high) {
int x = a[low];
while(low < high) {
while(low < high && x <= a[high]) {
high--;
}
if(low < high) {
a[low++] = a[high];
}
while(low < high && x >= a[low]) {
low++;
}
if(low < high) {
a[high--] = a[low];
}
a[low] = x;
}
return low;
}
void quick_sort(int *a, int low, int high) {
if(low < high) {
int pivot = partition(a, low, high);
quick_sort(a, low, pivot - 1);
quick_sort(a, pivot + 1, high);
}
}
int find_lost_positive(int *a, int n) {
int first_positive = 0, second_positive = 0;
int i;
int result = 0;
for(i = 0; i < n; i++) {
if(a[i] == 1)
break;
}
if(i >= n) {
return 1;
}
quick_sort(a, 0, n - 1);
for(i = 0; i < n; i++) {
if(a[i] > 0) {
if(first_positive == 0) {
first_positive = a[i];
}
if(second_positive == 0) {
second_positive = 0;
}
if(first_positive == (second_positive - 1)) {
first_positive = second_positive;
second_positive = 0;
} else {
result = first_positive + 1;
}
}
}
return result;
}
void main() {
int a[] = {9, 20, -2, -45, 23, 5, 1};
int n = sizeof(a) / sizeof(int);
int result = find_lost_positive(a, n);
printf("result = %d.\n", result);
getchar();
}