LeetCode第41题求解遇Address Sanitizer堆缓冲区溢出问题求助

直接问题：堆缓冲区溢出的原因 #

你的代码中堆缓冲区溢出的根源是冒泡排序的内层循环越界访问数组：

for (int j = 0; j < numsSize - i; j++) {
    if (nums[j] > nums[j + 1]) { 
        // 当j = numsSize - i - 1时，j+1 = numsSize - i
        // 当i=0时，j+1等于numsSize，超出数组索引的合法范围（最大索引为numsSize-1）
        int t = nums[j + 1];
        nums[j + 1] = nums[j];
        nums[j] = t;
    }
}

只需将内层循环的终止条件修改为j < numsSize - i - 1，即可避免越界：

for (int j = 0; j < numsSize - i - 1; j++) {
    // 交换逻辑不变
}

代码逻辑的效率问题（附加优化） #

即使修复了溢出问题，你的代码三重嵌套循环的时间复杂度为O(n³)，面对LeetCode的大规模测试用例会超时。LeetCode第41题要求的是O(n)时间、O(1)空间的解法，以下是符合要求的标准实现：

int firstMissingPositive(int* nums, int numsSize) {
    // 阶段1：将每个正整数放到对应的索引位置（数字x应放在索引x-1处）
    for (int i = 0; i < numsSize; ++i) {
        // 仅当当前数字是有效正整数、未在正确位置时，循环交换到正确位置
        while (nums[i] > 0 && nums[i] <= numsSize && nums[nums[i] - 1] != nums[i]) {
            int temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }

    // 阶段2：遍历数组，找到第一个不匹配的位置
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    // 若所有位置都匹配，说明缺失的是numsSize+1
    return numsSize + 1;
}

高效解法的逻辑说明 #

1. 利用数组作为哈希表：不需要额外空间，通过交换将每个正整数x放到索引x-1的位置，让数组的有效正整数按顺序排列。
2. 快速定位缺失值：遍历数组时，第一个不满足nums[i] == i+1的位置，i+1就是缺失的第一个正整数。如果所有位置都匹配，说明数组包含了1~numsSize的所有正整数，缺失的就是numsSize+1。

原代码的其他冗余问题 #

• 外层的k循环完全多余：无论第一个正整数出现在数组哪个位置，都应该从1开始检查缺失值。
• 当数组中存在极大值时（例如[100000]），你的代码会循环到max-1，导致无意义的性能损耗。

内容的提问来源于stack exchange，提问作者Om Bhardwaj