寻找最小正整数

2018

给定一个含n个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。

image-20230703093433045

1.试解

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//烂代码
#include "preset.h"

int listMax(SqList sql) {
    int res = sql.elem[0];
    for (int i = 1; i < sql.length; ++i) {
        if (sql.elem[i] > res) {
            res = sql.elem[i];
        }
    }
    return res;
}

int listMin(SqList sql) {
    int res = sql.elem[0];
    for (int i = 1; i < sql.length; ++i) {
        if (sql.elem[i] < res) {
            res = sql.elem[i];
        }
    }
    return res;
}

//listDelete删除指定元素
void listDelete(SqList &sql, int x) {
    int k = 0;
    for (int i = 0; i < sql.length; ++i) {
        if (sql.elem[i] == x) {
            k++;
        } else {
            sql.elem[i - k] = sql.elem[i];
        }
    }
    sql.length = sql.length - k;
}

int maxPositiveInt(SqList sql) {
    int min = listMin(sql);
    int max = listMax(sql);
    int i = 1;
    while (sql.length) {
        if (i < min) break;
        if (min == i) i++;
        //删除sql中的最小元素
        print(sql);
        listDelete(sql, min);
        //重新确定最小元素
        min = listMin(sql);
    }
    if (min == max) return max + 1;
    else return i;
}

int main() {
    //SqList sql = {{-5, 4, 1, 2, 3, 5, 6}, 7};
    //SqList sql = {{-5, 3, 2, 3}, 4};
    SqList sql = {{-5, -3, 1, 2, 3}, 5};
    cout << maxPositiveInt(sql);
    return 0;
}

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
//寻找数组中未出现的、最小的正整数
//设计一个在时间上尽可能高效的算法，找出数组中 未出现的 最小的 正整数

#include "preset.h"

int findMin(SqList sql) {
    int n = sql.length;
    int mark[n + 2] = {0};
    for (int i = 0; i < n; ++i) {
        if (sql.elem[i] > 0 && sql.elem[i] <= n + 1) mark[sql.elem[i]] = 1;
    }
    for (int i = 1; i <= n + 1; ++i) {
        if (mark[i] == 0) return i;
    }
    return -1;
}

int main() {
    //SqList sql = {{-5, 4, 1, 2, 3, 5, 6}, 7};
    SqList sql = {{-5, 3, 2, 3}, 4};
    //SqList sql = {{-5, -3, 1, 2, 3}, 5};
    cout << findMin(sql);
    return 0;
}