[数据结构与算法]关于LeetCode中官方对于Swift解题API的设计错误

问题

在LeetCode的题目 缺失的第一个正数 中，描述了这样一个问题：

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

注意题意中有一个额外的要求：请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

这个常量级别的额外空间的解决方案是怎么实现的？事实上，所谓的常量空间（即O(1)）解决方案，是建立在对传入参数nums的利用上的。

我们参见官方题解：缺失的第一个正数 - 官方题解 。

题解中给出的解法，以python3代码为例，是这样的：

# python3 实现
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if nums[i] <= 0:
                nums[i] = n + 1
        
        for i in range(n):
            num = abs(nums[i])
            if num <= n:
                nums[num - 1] = -abs(nums[num - 1])
        
        for i in range(n):
            if nums[i] > 0:
                return i + 1
        
        return n + 1

# 作者：LeetCode-Solution
# 链接：https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我们可以看到，正是因为python解题接口设计的nums是可写的，利用这一特性，才取巧的完成了O(1)额外空间的利用 - 因为nums不属于额外空间。

我们再看看C++ 的接口：

// c++ 接口
int firstMissingPositive(vector<int>& nums)

再看看Java接口：

// java接口
public int firstMissingPositive(int[] nums)

都是统一的nums可修改设计。可是，到了swift设计的接口就成了：

func firstMissingPositive(_ nums: [Int]) -> Int

有人问，这有什么问题？
答：当然有问题，问题就在于swift传入的的nums并不可修改。
例如如下代码：

class Solution {
    func firstMissingPositive(_ nums: [Int]) -> Int {
        // error: cannot assign through subscript: 
        // 'nums' is a 'let' constant in solution.swift
        nums[0] = 1 // 编译错误！
        return 0
    }
}

为什么，因为传入的nums是不可写的。

这虽然不妨碍用swift通过本题，但是题目描述中要求的 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案 将变得不可信任。因为无论你如何想破脑袋，用swift都无法解决。

正确的做法

正确的做法是用inout作为传入参数。

func firstMissingPositive(_ nums: inout [Int]) -> Int

这样nums才是可以修改的。

func firstMissingPositive(_ nums: inout [Int]) -> Int {
    nums[0] = 1
    return 0
}

总结和建议

我认为LeetCode在这道题上存在错误，这个错误主要在于不同语言的接口实现不统一上。如果要改正这个错误，只有两个选择：

1. 题目不再要求 只使用常数级别额外空间的解决方案 。
2. 修改swift的解题接口，统一以inout传递数组。

希望LeetCode工作人员能看到我的建议，希望LeetCode越来越好。