448. 找到所有数组中消失的数字

Easy

题目描述

给你一个含 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]

提示：

n == nums.length
1 <= n <= 10^5
1 <= nums[i] <= n

**进阶：**你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

解题思路

这道题有两种主要解法：

方法一：哈希表标记法 使用额外的哈希表或数组来标记每个数字是否出现过，然后遍历 [1, n] 找出未标记的数字。虽然简单直观，但需要 O(n) 的额外空间。

方法二：原地标记法（推荐） 利用题目的关键信息：数组中的数字都在 [1, n] 范围内，且数组长度为 n。我们可以通过修改原数组来标记数字的出现：

遍历数组，对于每个数字 nums[i]，将索引为 |nums[i]| - 1 的元素标记为负数
第二次遍历，如果某个位置的数字仍为正数，说明对应的数字（索引+1）没有出现过

这种方法巧妙地利用了数字的正负性来标记状态，既不需要额外空间，又能在 O(n) 时间内完成。

方法三：环形交换法 将每个数字放到它应该在的位置（nums[i] 应该在索引 nums[i]-1），最后检查哪些位置上的数字不匹配。

代码实现

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        // 原地标记法
        for (int i = 0; i < nums.size(); i++) {
            int index = abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        
        vector<int> result;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) {
                result.push_back(i + 1);
            }
        }
        
        return result;
    }
};

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        # 原地标记法
        for i in range(len(nums)):
            index = abs(nums[i]) - 1
            if nums[index] > 0:
                nums[index] = -nums[index]
        
        result = []
        for i in range(len(nums)):
            if nums[i] > 0:
                result.append(i + 1)
        
        return result

public class Solution {
    public IList<int> FindDisappearedNumbers(int[] nums) {
        // 原地标记法
        for (int i = 0; i < nums.Length; i++) {
            int index = Math.Abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        
        IList<int> result = new List<int>();
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] > 0) {
                result.Add(i + 1);
            }
        }
        
        return result;
    }
}

var findDisappearedNumbers = function(nums) {
    // 原地标记法
    for (let i = 0; i < nums.length; i++) {
        let index = Math.abs(nums[i]) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }
    
    let result = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            result.push(i + 1);
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

解法	时间复杂度	空间复杂度
原地标记法	O(n)	O(1)
哈希表法	O(n)	O(n)
环形交换法	O(n)	O(1)

推荐使用原地标记法，满足进阶要求的 O(1) 空间复杂度。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目