2018年的专业408算法题

2018年的专业408算法题

文章目录

• 0 结果
• 1 题目
• 2 思路
• • 2.1 思路1（暴力解：枚举）
  • 2.2 思路2（较优解：排序后扫描数组）
  • 2.3 思路3（最优解：空间换时间）
• 附录

0 结果

1 题目

2 思路

2.1 思路1（暴力解：枚举）

枚举所有可能出现的最小正整数，扫描数组判断元素是出现，若没有出现，则输出。

#include <cstdio>int ans(int A[], int n){bool flag;for(int i = 1; i < n + 1; i++){flag = false;for (int j = 0; j < n; ++j) {if(A[j] == i){flag = true;break;}}if(flag == false){return i;}}return n + 1;
}int main(){int A[] = {-5, 3, 2, 3};//int A[] = {1, 2, 3};const int n = sizeof(A)/ sizeof(*A);for (int i = 0; i < n; ++i) {printf("%d ", A[i]);}printf("n%d", ans(A, n));ans(A, n);return 0;
}

时间复杂度： O ( n 2 ) O(n^2) O(n2)
空间复杂度： O ( 1 ) O(1) O(1)

2.2 思路2（较优解：排序后扫描数组）

对数组使用快速排序得到升序数组，然后便利数组得到第一个未出现的最小正整数。

#include <cstdio>
#include <cstdlib>
#include <algorithm>//快排
void Qsort(int A[], int L, int R){if(L >= R) return;int pivot, i = L, j = R;std::swap(A[L], A[rand()%(R - L + 1) + L]);//快拍优化pivot = A[L];//作为比较的基准值while(i < j){while(i < j && A[j] > pivot) j--;while(i <j && A[i] <= pivot) i++;if(i < j)std::swap(A[i], A[j]);}std::swap(A[L], A[i]);Qsort(A, L, i - 1);Qsort(A, i + 1, R);
}int ans(int A[], int n){Qsort(A, 0, n - 1);int i = 0;while(i < n && A[i] <= 0){i++;}if(i == n) return 1;//数组A全是非正整数for(int j = i, k = 1;j < n;j++, k++){//j为数组A的下标，k为比较的正整数if(k != A[j]) return k;}return A[n-1] + 1;
}int main(){//int A[] = {-5, 3, 2, 3};int A[] = {1, 2, 3};const int n = sizeof(A)/ sizeof(*A);for (int i = 0; i < n; ++i) {printf("%d ", A[i]);}printf("n%d", ans(A, n));ans(A, n);return 0;
}

时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度： O ( 1 ) O(1) O(1)

2.3 思路3（最优解：空间换时间）

因为时间高效，则采用空间换时间的方法。
方法：打表计数【数组大小设为n，即元素的个数】。
遍历数组出现number,如果范围在[1,n]之间，则记[number-1]次数为1，遍历完数组后，指标i从[0,n)开始递增判断表值是否为0，是则跳出循环,最后输出i+1。

#include <cstdio>
#include <cstdlib>int ans(int A[], int n){int* cnt;cnt = (int*)malloc(sizeof(int)*n);for (int i = 0; i < n; ++i) {*(cnt + i) = 0;}for (int j = 0; j < n; ++j) {if(A[j] > 0 && A[j] <= n){*(cnt + A[j] - 1) = 1;}}int k;for (k = 0; k < n; ++k) {if(cnt[k] == 0) break;}return k + 1;}int main(){int A[] = {-5,3,2,3};//1,2,3const int n = sizeof(A)/ sizeof(*A);for (int i = 0; i < n; ++i) {printf("%d ", A[i]);}printf("n%d", Func(A, n));return  0;
}

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)

附录

408历年真题算法题解析