Leetcode 41. First Missing Positive

题目

41. First Missing Positive

Difficulty: Hard
Total Accepted: 152.5K
Total Submissions: 571.7K

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1, 2, 0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

题目链接

解题报告

AC 截图

题目大意

本题要求寻找到一串未排序的整数中，缺失的最小的正整数。同时要求 $O(n)$ 级的时间复杂度和常量级的空间开销。

解题思路

最容易想到的解题方法莫过于从 1 开始，将正整数依次在整个数组中寻找一遍。但是这种在无序数组上进行的扫描，时间复杂度为 $O(n^2)$，显然是不符合要求的。

另一个容易想到的方法是建立一个等规模的布尔数组，初始值为 false，然后扫描一次原始数组，将对应下标的布尔值置为 true。最后扫描一遍布尔数组，即可以以 $O(n)$ 的时间复杂度完成。但是这种方法需要开辟一个变长的空间，不符合题目「常量级空间开销」的要求。

那么要如何优化这两种方法，来满足题目要求呢？

从第一种方法出发，既然无序的数组上扫描会超时，那么我们就尝试在 $O(n)$ 时间复杂度内构建一个“特殊的”有序数组即可。

从第二种方法出发，既然不允许变长的额外空间开销，那么我们就尝试使用原数组的空间来作为“布尔数组”即可。

两种方法的优化最后都指向同一个解法：先对原数组进行操作，使之可以在一次扫描后得出结果。

那么如何进行操作呢？我们知道，我们的目标是寻找缺失的最小的正整数，那么我们可以吧所有数字放到其对应的位置（比如数字 1 放到下标为 0 的位置上，数字 4 放到下标为 3 的位置上），这样一来，array[index] == index + 1 这些布尔值就构成了第二种方法中的“布尔数组”，不满足这个条件的最小的 index，对应的数字 index + 1 就是题解。

构建数组的过程也是简单的，顺序扫描整个数组，不断将当前位置的数字和其应该处于的位置上的数字进行交换，就可以在 $O(n)$ 的时间复杂度下完成操作。再加上最后的扫描求解，整个解法的复杂度为 $O(n)$.

题解1

C++ 代码

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {        
        int index, length;
        length = nums.size();
        
        for (index = 0; index < length; ++index) {
            while (nums[index] > 0 && nums[index] <= length && 
                    nums[index] != nums[nums[index] - 1]) {
                swap(nums[index], nums[nums[index] - 1]);
            }
        }
        
        for (index = 0; index < length; ++index) {
            if (nums[index] != index + 1) {
                return index + 1;
            }
        }
        
        return length + 1;
    }
};

AC 截图

题解分析

虽然这个题解顺利通过了测试，但是竟然还有 16.03% 的更优解？是我算法的问题吗？

打开最优解的示例代码一看：

class Solution {
public:
    // time: O(n), space: O(1)
    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[i], nums[nums[i] - 1]);
            }
        }
        
        for (int i = 0; i < n; i ++) {
            if (nums[i] != i + 1)
                return i + 1;
        }
        
        return n+1;    
    }
};

乍一眼看过去……这不和我是一样的吗？而且 i++ 的效率显然不如 ++i，怎么可能还比我快？他甚至还在每个 for 循环中重新声明变量 i，这肯定是比我直接声明好进行复用要更慢啊！不信邪的我也改了一下自己的代码，于是有了题解2……

题解2（最优解）

c++ 代码

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {        
        int length;
        length = nums.size();
        
        for (int index = 0; index < length; ++index) {
            while (nums[index] > 0 && nums[index] <= length && 
                    nums[index] != nums[nums[index] - 1]) {
                swap(nums[index], nums[nums[index] - 1]);
            }
        }
        
        for (int index = 0; index < length; ++index) {
            if (nums[index] != index + 1) {
                return index + 1;
            }
        }
        
        return length + 1;
    }
};

AC 截图

题解分析

看样子确实是重新声明的写法会更快……但……为什么复用的效率反而不如每次重新声明高？这不科学！我不接受！

如何找到问题的源头呢？当然是反汇编啦～

测试代码：

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
  int solve1(vector<int>& nums) {
    int length;
    length = nums.size();

    for (int index = 0; index < length; index++) {
      while (nums[index] > 0 && nums[index] <= length &&
        nums[index] != nums[nums[index] - 1]) {
        swap(nums[index], nums[nums[index] - 1]);
      }
    }

    for (int index = 0; index < length; index++) {
      if (nums[index] != index + 1) {
        return index + 1;
      }
    }

    return length + 1;
  }

  int solve2(vector<int>& nums) {
    int index, length;
    length = nums.size();

    for (index = 0; index < length; index++) {
      while (nums[index] > 0 && nums[index] <= length &&
        nums[index] != nums[nums[index] - 1]) {
        swap(nums[index], nums[nums[index] - 1]);
      }
    }

    for (index = 0; index < length; index++) {
      if (nums[index] != index + 1) {
        return index + 1;
      }
    }

    return length + 1;
  }
};

int main()
{
  Solution ins;
  vector<int> input = { 1, 2, 0 };
  auto ans = ins.solve1(input); ans = ins.solve2(input);
  return 0;
}

Windows 汇编：solve1

Windows 汇编：solve2

令人吃惊的是：两者的汇编代码几乎是完全一样的！唯一的区别在于：由于 index 和 length 的声明先后顺序不同，其在内存中的地址（相对于ebp）在两个函数中对调了。这虽然没能验证反复声明反而更快的结果，但至少说明了 在 for 循环初始化语句中声明变量，不会比在外部声明更耗时。同时也告诉我们，单纯通过高级语言编写中的直觉推测程序在机器上执行的效率是危险的。

那么，为什么 solve2 会更快呢？事实上，经过测试，在 Windows VS 环境下，二者速度是基本一致的。那么是编译器和环境的问题吗？

查找 Leetcode 的编译环境，我了解到其使用的是 G++ 6.4，C++14 标准。于是我在 MacOS 环境下对于其使用 g++ 进行编译，并且利用 objdump 得到汇编结果，通过重定向保存到 main.s 文件内：