Given an array say [9,20,-2,-45,23,5,1], find the minimum positive missing number from the array.
解决这个问题有两种思路：第一种就是应用hash表来记录，不考虑所有的负数，首先我们找到数组中最大的正数，比如说这个数组中的23，然后分配23个空间，所有值都标记为0，然后遍历数组，如果对应的正数出现，就标记为1，这样，遍历整个数组之后就把所有出现的正数都记录了下来。然后重新遍历hash表，遇到一个值为0的就是我们要找的那个正数。这种方法的时间复杂是O(n)，但是空间复杂度要随着数组中的最大数的改变而改变，一旦最大数变的很大，空间复杂度就会太高了。所以这个方法还是不太好。第二种方法就是给数组排序，使用快速排序的时间复杂度是O(nlogn), 排血之后所有的负数都可以pass掉了。从正数开始，设置两个记录，记录当前正数和当前正数的前一个正数，再对这两个数进行比较，如果前一个正数+1等于当前正数，那么继续遍历数组，如果不等于，那么我们要找的数就是当前正数的前一个数+1。这就是我们丢失的最小正数。同时还要考虑特殊的情况，就是所有数值都是0或者所有数值都是负数的情况，这些直接都返回1就好了。排序的时间复杂度是O(nlogn)加上查找时间O(n)。下面给出详细代码：
[cpp]
#include<stdio.h>
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();
}
补充：软件开发 , C++ ,
