0%

数据结构算法每日一练(七)数组未出现最小正整数

数据结构算法每日一练(七)数组未出现最小正整数

难度: ⭐⭐

题目:给定一个含n(n≥1)个整数的数组A,请设计一个在时间上尽可能高效的算法。找出数组中未出现的最小正整数。例如,数组{-5,3,2,3}

中未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是4。要求:

1)给出算法的基本设计思想。

2)根据设计思想,来用C或C++语言描述算法,关键之处给出注释。

3)说明你所设计算法的时问复杂度和空问复杂度。

(1)基本思想: 时间上尽可能高效的算法,采用空间换时间的方式,采用桶排序算法思想。分配一个用于标记的数组 B[n],用来记录A中是否出现了 1 ~ n 中的正整数,B[0]对应正整数 1,B[n-1]对应正整数 n,初始化B中全部为 0。由于A中含有n个整数,因此可能返回的值是 1 ~ n+1,当A中n个数恰好为 1 ~ n时返回 n+1。当数组A中出现了小于等于0或大于n的值时,会导致 1 ~ n中出现空余位置,返回结果必然在 1 ~ n中,因此对于A中出现了小于等于 0或大于n的值,可以不采取任何操作。

经过以上分析可以得出算法流程:

  1. 从A[0]开始遍历A,若 0 < A[i] <= n,则令 B[A[i]-1]=1;否则不做操作。
  2. 对A遍历结束后,开始遍历数组B,若能查找到第一个满足 B[i]==0 的下标 i,返回i+1即为结果,此时说明A中未出现的最小正整数在 1~n之间。
  3. 若 B[i]全部不为0,返回i+1(跳出循环时 i=n, i+1 等于n+1),此时说明A中未出现的最小正整数是n+1。

本题思想与上道数组主元素算法一基本思想相同

(2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <string.h>
using namespace std;
int findMissMin(int A[], int n) {
int *B;
B = (int *)malloc(sizeof(int)*n); //分配空间
memset(B, 0, sizeof(int)*n); //赋初值为0
for (int i = 0; i < n; i++) { //遍历A数组
if (A[i] > 0 && A[i] <= n) { //若A[i]的值介于1~n,则标记数组B
B[ A[i] - 1] = 1;
}
}//for
for (int i = 0; i < n; i++) { //遍历B数组,找到未出现的最小正整数
if (B[i] == 0) {
return i + 1; //返回结果
}
}//for
}
int main() {
int A[] = {-3, 0, -4, 1, 5, 2, 6, 3, 4, 8};
int n = sizeof(A) / sizeof(A[0]);
int res = findMissMin(A, n);
cout << res << endl;
return 0;
}

(3)

时间复杂度为$O(n)$,空间复杂度为$O(n)$

北以晨光 wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
------ 本文结束感谢您的阅读 ------