解決這個問題有兩種思路：第一種就是應用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(); }
