LeetCode 645. 错误的集合

Categories:

题目描述
思路分析
1. 解法一：哈希表计数（推荐）
2. 解法二：位运算（异或）
相似题目

题目描述

✅ 645. 错误的集合

思路分析

解法一：哈希表计数（推荐）

核心思路：

使用哈希表统计每个数字出现的次数

遍历 [1, n]，出现两次的数字即为重复数字，缺失的数字即为未出现的数字

两次线性扫描即可得到答案

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，两次线性扫描

空间复杂度：O(n)，哈希表存储各元素计数

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;

        // 统计每个数字出现次数
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        int dup = -1, missing = -1;

        // 遍历 [1, n]，找出重复和缺失的数字
        for (int i = 1; i <= n; i++) {
            int cnt = count.getOrDefault(i, 0);
            if (cnt == 2) {
                dup = i;
            } else if (cnt == 0) {
                missing = i;
            }
        }

        return new int[]{dup, missing};
    }
}

func findErrorNums(nums []int) []int {
    n := len(nums)

    // 统计每个数字出现次数
    count := make(map[int]int, n)
    for _, num := range nums {
        count[num]++
    }

    dup, missing := -1, -1

    // 遍历 [1, n]，找出重复和缺失的数字
    for i := 1; i <= n; i++ {
        cnt := count[i]
        if cnt == 2 {
            dup = i
        } else if cnt == 0 {
            missing = i
        }
    }

    return []int{dup, missing}
}

解法二：位运算（异或）

核心思路：

将数组中所有元素与 [1, n] 中所有元素进行异或，得到 dup XOR missing

利用差值或求和公式辅助区分重复数与缺失数：sum(nums) - sum([1,n]) = dup - missing

联立两个方程即可求解

复杂度分析：

时间复杂度：O(n)，一次线性扫描

空间复杂度：O(1)，仅使用常数额外空间

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;

        // 利用求和差值：sum(nums) - sum(1..n) = dup - missing
        long sumNums = 0;
        long sumExpected = (long) n * (n + 1) / 2;
        Set<Integer> seen = new HashSet<>();
        int dup = -1;

        for (int num : nums) {
            sumNums += num;
            if (!seen.add(num)) {
                dup = num;
            }
        }

        // missing = dup - (sumNums - sumExpected)
        int missing = (int) (dup - (sumNums - sumExpected));

        return new int[]{dup, missing};
    }
}

func findErrorNums(nums []int) []int {
    n := len(nums)

    // 利用求和差值：sum(nums) - sum(1..n) = dup - missing
    sumNums := 0
    sumExpected := n * (n + 1) / 2
    seen := make(map[int]bool, n)
    dup := -1

    for _, num := range nums {
        sumNums += num
        if seen[num] {
            dup = num
        }
        seen[num] = true
    }

    // missing = dup - (sumNums - sumExpected)
    missing := dup - (sumNums - sumExpected)

    return []int{dup, missing}
}

相似题目

题目	难度	考察点
41. 缺失的第一个正数	困难	数组原地哈希
136. 只出现一次的数字	简单	位运算
137. 只出现一次的数字 II	中等	位运算
268. 丢失的数字	简单	哈希表/位运算
448. 找到所有数组中消失的数字	简单	原地标记
287. 寻找重复数	中等	快慢指针/二分

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/10619280