当前位置：首页 > article >正文

【Leetcode-找到所有数组中消失的数字】利用标记出现数组中出现过的数字解决数组中消失的数字问题

article 2025/1/13 2:07:40

题目描述

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例1

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例2

输入：nums = [1,1]
输出：[2]

解题思路（时间复杂度O(n)）

#include <stdlib.h>

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {

    int* appeared = (int*)calloc(numsSize, sizeof(int)); // 初始化标记数组：appeared数组用于标记1到n之间的数字是否在nums中出现。数组初始化为0，表示所有数字初始时都未出现。

    int* ret = (int*)malloc(numsSize * sizeof(int));
    int retIndex = 0; 

    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > 0 && nums[i] <= numsSize) { // 标记出现的数字：遍历nums数组，对于每个数字nums[i]，如果它在1到n之间，则将appeared[nums[i] - 1]标记为1。这里减1是因为数组索引从0开始。
            appeared[nums[i] - 1] = 1; 
        }
    }

    for (int i = 0; i < numsSize; i++) { // 找到未出现的数字：再次遍历appeared数组，对于每个未标记的数字（即appeared[i] == 0），将i + 1（因为数字从1开始）添加到返回数组ret中。
        if (appeared[i] == 0) {
            ret[retIndex++] = i + 1; 
        }
    }

    *returnSize = retIndex; // 设置返回数组的大小：returnSize指向返回数组的大小，即retIndex。

    free(appeared); // 释放标记数组：释放appeared数组，避免内存泄漏。

    return ret; 
}