Easy

题目描述

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。

给定一个数组 nums 代表了集合 s 发生错误后的结果。

请你找出重复出现的整数，再找出丢失的整数，将它们以数组的形式返回。

示例 1：

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

示例 2：

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

提示：

  • 2 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^4

解题思路

这道题需要找出一个重复的数字和一个丢失的数字。有几种解法：

方法一：哈希表统计（推荐）

  • 遍历数组，用哈希表统计每个数字的出现次数
  • 再遍历 1 到 n，找出出现次数为 2 的数字（重复）和出现次数为 0 的数字（丢失）
  • 时间复杂度 O(n)，空间复杂度 O(n)

方法二：数学方法

  • 设重复数字为 x，丢失数字为 y
  • 利用求和公式：sum(nums) - sum(1…n) = x - y
  • 利用平方和公式：sum(nums²) - sum(1²…n²) = x² - y²
  • 联立方程求解 x 和 y

方法三：原地标记

  • 利用数组下标，将访问过的位置标记为负数
  • 如果发现某位置已经是负数，说明对应数字重复
  • 最后遍历找出仍为正数的位置，对应丢失的数字

这里实现哈希表方法，代码简洁易懂且效率较高。

代码实现

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> count;
        
        // 统计每个数字出现次数
        for (int num : nums) {
            count[num]++;
        }
        
        int duplicate = -1, missing = -1;
        
        // 找出重复和丢失的数字
        for (int i = 1; i <= n; i++) {
            if (count[i] == 2) {
                duplicate = i;
            } else if (count[i] == 0) {
                missing = i;
            }
        }
        
        return {duplicate, missing};
    }
};

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        count = {}
        
        # 统计每个数字出现次数
        for num in nums:
            count[num] = count.get(num, 0) + 1
        
        duplicate = missing = -1
        
        # 找出重复和丢失的数字
        for i in range(1, n + 1):
            if count.get(i, 0) == 2:
                duplicate = i
            elif count.get(i, 0) == 0:
                missing = i
        
        return [duplicate, missing]

public class Solution {
    public int[] FindErrorNums(int[] nums) {
        int n = nums.Length;
        Dictionary<int, int> count = new Dictionary<int, int>();
        
        // 统计每个数字出现次数
        foreach (int num in nums) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
        }
        
        int duplicate = -1, missing = -1;
        
        // 找出重复和丢失的数字
        for (int i = 1; i <= n; i++) {
            int currentCount = count.ContainsKey(i) ? count[i] : 0;
            if (currentCount == 2) {
                duplicate = i;
            } else if (currentCount == 0) {
                missing = i;
            }
        }
        
        return new int[] {duplicate, missing};
    }
}

var findErrorNums = function(nums) {
    const n = nums.length;
    const seen = new Set();
    let duplicate = 0;
    let sum = 0;
    
    for (let num of nums) {
        if (seen.has(num)) {
            duplicate = num;
        }
        seen.add(num);
        sum += num;
    }
    
    const expectedSum = n * (n + 1) / 2;
    const missing = expectedSum - sum + duplicate;
    
    return [duplicate, missing];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型哈希表方法
时间复杂度O(n)
空间复杂度O(n)

其中 n 为数组长度。需要遍历数组一次统计频次，再遍历 1 到 n 找出结果，总时间复杂度为 O(n)。使用哈希表存储计数信息，空间复杂度为 O(n)。

相关题目