本文共 2478 字，大约阅读时间需要 8 分钟。
今天我在学习一些算法题，遇到了一个挺有意思的问题，想来记录一下我的思考过程。问题描述是这样的：给定一个整数向量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)的时间复杂度内找到数组中的第一个缺失的正整数。总结一下，这就是我解决这个问题的思路和方法。通过交换数组中的元素，可以有效地找到缺失的正整数，并且时间复杂度非常高效。找出数组中第一个缺失的正整数 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; } }
转载地址：http://kigyk.baihongyu.com/