力扣面试03.04题 解题思路和步骤 C++实现带注释,事业单位面试题型及答题技巧

题目概述

力扣面试03.04题是一个关于数组和双指针技巧的编程问题。题目要求给定一个未排序的数组，找出其中没有出现的最小的正整数。这个问题可以通过多种方法解决，但本文将重点介绍一种高效且易于理解的方法：使用双指针技巧。

解题思路

解题的关键在于理解数组的特性和双指针技巧的应用。我们需要对数组进行一次遍历，将每个元素放置到其对应的索引位置上，数字2应该放在索引1的位置。使用双指针遍历数组，找到第一个不符合规则的元素，即该元素不等于其索引加1的位置，那么该位置的索引加1就是我们要找的最小正整数。

步骤实现

以下是解题步骤的具体实现：我们遍历数组，将每个元素移动到其正确的位置；我们再次遍历数组，找到第一个不符合规则的元素，从而确定答案。

C++代码实现

#include <vector>
#include <iostream>

int firstMissingPositive(std::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]) {
            std::swap(nums[i], nums[nums[i] - 1]);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

int main() {
    std::vector<int> nums = {3, 4, -1, 1};
    std::cout << "The first missing positive integer is " << firstMissingPositive(nums) << std::endl;
    return 0;
}