方法一：哈希表

本方法为暴力解。

哈希表是一个可以支持快速查找的数据结构：给定一个元素，我们可以在 O(1) 的时间查找该元素是否在哈希表中。

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>
#include "uthash.h"

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey;
        tmp->val = ival;
        HASH_ADD_INT(hashtable, key, tmp);
    } else {
        it->val = ival;
    }
}

int firstMissingPositive(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; i++) {
        insert(nums[i], 1);
    }
    for (int i = 1; i <= numsSize; i++) {
        struct hashTable* it = find(i);
        if (it == NULL) {
            return i;
        }
    }
    return numsSize + 1;
}

int main() {
    int a[] = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a, 4);
    printf("%d", miss);
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    unordered_set<int> st;
    for (int num : nums) {
        st.insert(num);
    }
    for (int i = 1; i <= n; ++i) {
        if (!st.count(i)){
            return i;
        }
    }
    return n + 1;
}

int main(int argc, const char * argv[]) {
    vector<int> a = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a);
    cout << miss;
    return 0;
}

这里可以用数组作为哈希表进行优化，由于结果 x 一定满足 1≤x≤n+1 ，所以只需要记录值在这个范围中的元素，修改如下：

C代码如下（含测试用例）：

#include <stdio.h>
#include <string.h>

int firstMissingPositive(int* a, int n){
    int f[n + 1];
    memset(f, 0, sizeof(f));
    for (int i = 0; i < n; i++) {
        if (a[i] > 0 && a[i] <= n) {
            f[a[i]] = 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (f[i] == 0) {
            return i;
        }
    }
    return n + 1;
}

int main() {
    int a[] = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a, 4);
    printf("%d", miss);
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

int firstMissingPositive(vector<int>& nums) {
    int n = (int) nums.size();
    vector<bool> flag(n + 1, false);
    for (int num: nums) {
        if (num > 0 && num <= n) {
            flag[num] = true;
        }
    }
    for (int i = 1; i <= n; i++) { // 从1开始遍历flag数组
        if (!flag[i]) {
            return i; // 第一个位置为false的就是缺失的最小正整数
        }
    }
    return n + 1; // 位置均为true，没有缺失正数返回n+1
}

int main(int argc, const char * argv[]) {
    vector<int> a = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a);
    cout << miss;
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。
• 空间复杂度： O(n) ，需要开辟大小为 O(n) 的辅助哈希表。

方法二：原地哈希

这个思路非常巧妙，用负号标记元素存在。将数组的下标假想为哈希表的键。

算法的流程如下：

• 我们将数组中所有小于或等于 0 的数修改为 n+1 ；
• 我们遍历数组中的每一个数 x ，它可能已经被打了标记，因此原本对应的数为 |x| 。如果 |x|∈[1,n] ，那么我们给数组中的第 |x|−1 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；
• 在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 n+1 ，否则答案是第一个正数的位置加 1 。

C代码如下（含测试用例）：

#include <stdio.h>

int firstMissingPositive(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] <= 0) {
            nums[i] = numsSize + 1;
        }
    }
    for (int i = 0; i < numsSize; ++i) {
        int num = abs(nums[i]);
        if (num <= numsSize) {
            nums[num - 1] = -abs(nums[num - 1]);
        }
    }
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }
    return numsSize + 1;
}

int main() {
    int a[] = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a, 4);
    printf("%d", miss);
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

int firstMissingPositive(vector<int>& nums) {
    int n = (int)nums.size();
    for (int& num : nums) {
        if (num <= 0) {
            num = n + 1; //越界数字处理
        }
    }
    for (int i = 0; i < n; ++i) {
        int num = abs(nums[i]);
        if (num <= n) { //合格的数字
            nums[num - 1] = -abs(nums[num - 1]); //-标记,正确数字对应的位置
        }
    }
    for (int i = 0; i < n; ++i) { //找到第一个为正数的位置
        if (nums[i] > 0) {
            return i + 1; //位置下标+1为缺失数
        }
    }
    return n+1;
}

int main(int argc, const char * argv[]) {
    vector<int> a = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a);
    cout << miss;
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。
• 空间复杂度： O(1) 。

方法三：置换

除了打标记以外，我们还可以使用置换的方法。

在恢复后，数组应当有{1, 2, ..., n}的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。以{3, 4, -1, 1}为例，恢复后的数组应当为{1, -1, 3, 4}，我们就可以知道缺失的数为2。

由于每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为 n ，整个方法的时间复杂度为 O(n) 。

C代码如下（含测试用例）：

#include <stdio.h>

int firstMissingPositive(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; ++i) {
        while (nums[i] > 0 && nums[i] <= numsSize &&
               nums[nums[i] - 1] != nums[i]) {
            int t = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i], nums[i] = t;
        }
    }
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return numsSize + 1;
}

int main() {
    int a[] = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a, 4);
    printf("%d", miss);
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <vector>
using namespace std;

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            swap(nums[nums[i] - 1], nums[i]);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

int main(int argc, const char * argv[]) {
    vector<int> a = {-5, 3, 2, 3};
    int miss = firstMissingPositive(a);
    cout << miss;
    return 0;
}

复杂度分析

• 时间复杂度： O(n) 。
• 空间复杂度： O(1) 。