本文共 2478 字，大约阅读时间需要 8 分钟。

   
    
        
    
    
    
    
        
     
            
      
                
       
                    
                        class Solution {
                        public:
                            int firstMissingPositive(vector
         
           A) {
                                int n = A.size();
                                for (int i = 0; i < n; ++i) {
                                    while (A[i] > 0 && A[i] <= n && A[A[i] - 1] != A[i]) {
                                        swap(A[i], A[A[i] - 1]);
                                    }
                                }
                                for (int i = 0; i < n; ++i) {
                                    if (A[i] != i + 1) {
                                        return i + 1;
                                    }
                                }
                                return n + 1;
                            }
                        }
                    
         
                
            
      
        
     
    
    
   
今天我在学习一些算法题，遇到了一个挺有意思的问题，想来记录一下我的思考过程。
问题描述是这样的：给定一个整数向量A，找出第一个缺失的正整数。举个例子，比如数组中的数字是[1,2,3,4]，那么返回1；如果是[1,3,4,5]，返回2；如果是[2,3,4,5]，返回1。
我觉得这个问题挺有意思的，想通过一些方法来解决它。于是，我决定仔细分析问题，找出解决方案。
首先，我想到了一个常见的解决方法。这个方法的核心思想是通过交换来找到缺失的数字。具体来说，就是遍历数组，对于每个数字A[i]，如果它大于0，并且小于等于数组的长度n，同时它前面的数字不等于它，那么就交换这两个位置的值。
让我用一个例子来说明这个过程。假设数组是[2,3,4,5]，n=5。我们从左到右遍历每个元素：
第一个元素是2，检查它是否大于0且小于等于5。然后看A[2-1]=A[1]=3是否等于2。因为不等于，所以交换这两个位置，数组变成[3,2,4,5]。
接着，第二个元素是2，继续检查。现在A[2-1]=A[1]=2，已经和当前元素相等了，所以跳出循环。
然后，第三个元素是4，A[4-1]=A[3]=5不等于4，所以交换，数组变为[3,2,5,4]。
第四个元素是5，A[5-1]=A[4]=4不等于5，交换后数组变为[3,2,5,4]。
这样，整个数组处理完毕后，变成了[3,2,5,4]。然后我们再检查每个位置是否等于其索引+1。发现位置0的值是3，而索引是0，所以3≠1，于是返回1。
这个方法看起来有点绕，但其实它的核心思想是通过交换来找到最小的缺失值。这种方法的时间复杂度是O(n)，空间复杂度是O(1)，因为我们只交换了数组中的元素，并没有额外使用空间。
接下来，我想验证一下这个方法是否正确。通过几个例子来测试：
例子1：A = [1,2,3,4]，n=4
遍历每个元素：
第一个元素1，A[0]=1，检查A[1-1]=A[0]=1，相等，跳过。
第二个元素2，检查A[2-1]=A[1]=2，相等，跳过。
第三个元素3，检查A[3-1]=A[2]=3，相等，跳过。
第四个元素4，检查A[4-1]=A[3]=4，相等，跳过。
然后检查每个位置，A[i]是否等于i+1。发现都满足条件，所以返回n+1=5。
例子2：A = [1,3,4,5]，n=5
第一个元素1，检查A[0]=1，相等，跳过。
第二个元素3，检查A[3-1]=A[2]=4，4≠3，交换后数组变为[1,4,3,5]。
第三个元素3，检查A[3-1]=A[2]=3，相等，跳过。
第四个元素5，检查A[5-1]=A[4]=5，相等，跳过。
最后，检查数组，发现位置1的值是4，索引1+1=2，所以返回2。
例子3：A = [2,3,4,5]，n=5
第一个元素2，检查A[2-1]=A[1]=3，3≠2，交换后数组变为[3,2,4,5]。
第二个元素2，检查A[2-1]=A[1]=2，相等，跳过。
第三个元素4，检查A[4-1]=A[3]=5，5≠4，交换后数组变为[3,2,5,4]。
第四个元素4，检查A[4-1]=A[3]=4，相等，跳过。
检查数组，发现位置0的值是3，索引0+1=1，所以返回1。
通过这些例子，我发现这个算法是正确的。它能够在O(n)的时间复杂度内找到数组中的第一个缺失的正整数。
总结一下，这就是我解决这个问题的思路和方法。通过交换数组中的元素，可以有效地找到缺失的正整数，并且时间复杂度非常高效。