如何优化Kotlin中寻找缺失最小正整数的函数以提升大列表性能？

问题描述 #

需要实现一个接收整数列表、返回列表中不存在的最小正整数的函数，例如输入列表[1, 3, 6, 4, 1, 2]时，函数应返回5。以下是当前实现的Kotlin代码：

fun smallestMissingPositiveInteger(inputList: List<Int>): Int {
    val sortedList = inputList.filter { it > 0 }.sorted()
    var smallestMissing = 1
    
    for (i in sortedList) {
        if (i == smallestMissing) {
            smallestMissing++
        } else if (i > smallestMissing) {
            return smallestMissing
        }
    }
    
    return smallestMissing
}

当前代码在多数场景下可正常运行，但担忧其处理大型输入列表时的性能表现，请问在Kotlin中是否有更高效的实现方式？

更高效的实现方案 #

当前实现的时间复杂度为O(n log n)，主要开销来自排序操作，对于超大型列表确实会存在性能瓶颈。以下是两种更优的实现思路：

方法一：原地哈希法（时间O(n)，空间O(1)） #

这是性能最优的解法，核心逻辑是利用数组索引作为天然的“哈希映射”，将每个正整数放到其对应的索引位置（比如数字1对应索引0，数字2对应索引1），之后遍历数组找到第一个索引与值不匹配的位置，对应的正整数就是缺失的最小值。

Kotlin实现代码：

fun smallestMissingPositiveInteger(nums: List<Int>): Int {
    val arr = nums.toMutableList()
    val n = arr.size
    
    // 将所有非正整数替换为n+1（缺失的最小正整数必在1~n+1范围内）
    for (i in arr.indices) {
        if (arr[i] <= 0) {
            arr[i] = n + 1
        }
    }
    
    // 用负数标记对应索引的数字已存在
    for (i in arr.indices) {
        val num = kotlin.math.abs(arr[i])
        if (num <= n) {
            arr[num - 1] = -kotlin.math.abs(arr[num - 1])
        }
    }
    
    // 找到第一个正数对应的索引+1，即为缺失的最小正整数
    for (i in arr.indices) {
        if (arr[i] > 0) {
            return i + 1
        }
    }
    
    // 若1~n都存在，返回n+1
    return n + 1
}

方法二：HashSet辅助法（时间O(n)，空间O(n)） #

如果对空间要求不严格，这种方法实现更简洁：用HashSet存储所有正整数，从1开始逐个检查是否存在，直到找到第一个不存在的数字。时间复杂度同样为O(n)，但需要额外的O(n)空间存储集合。

Kotlin实现代码：

fun smallestMissingPositiveInteger(nums: List<Int>): Int {
    val positiveNums = nums.filter { it > 0 }.toHashSet()
    var smallestMissing = 1
    while (positiveNums.contains(smallestMissing)) {
        smallestMissing++
    }
    return smallestMissing
}

性能对比 #

• 原实现：时间O(n log n)，空间O(n)（存储排序后的新列表）
• 原地哈希法：时间O(n)，空间O(1)（仅修改原列表的可变副本，无额外大空间占用）
• HashSet法：时间O(n)，空间O(n)（存储正整数集合）

对于超大型列表，原地哈希法的性能优势最显著；如果追求代码简洁性，HashSet法是更易维护的选择。

内容的提问来源于stack exchange，提问作者Bhavesh Salunke