Info

数据结构精品课 和 递归算法专题课 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
645. Set Mismatch	645. 错误的集合	🟢

今天就聊一道很看起来简单却十分巧妙的问题，寻找缺失和重复的元素。之前的一篇文章 常用的位操作 中也写过类似的问题，不过这次的和上次的问题使用的技巧不同。

这是力扣第 645 题「错误的集合」，我来描述一下这个题目：

给一个长度为 N 的数组 nums，其中本来装着 [1..N] 这 N 个元素，无序。但是现在出现了一些错误，nums 中的一个元素出现了重复，也就同时导致了另一个元素的缺失。请你写一个算法，找到 nums 中的重复元素和缺失元素的值。

// 返回两个数字，分别是 {dup, missing}
int[] findErrorNums(int[] nums);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 返回两个数字，分别是 {dup, missing}
vector<int> findErrorNums(vector<int>& nums);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

# 返回两个数字，分别是 {dup, missing}
def findErrorNums(nums: List[int]) -> List[int]:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 返回两个数字，分别是 {dup, missing}
func findErrorNums(nums []int) []int {

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 返回两个数字，分别是 {dup, missing}
var findErrorNums = function(nums) {
    // 在新的数组中，1 到 n 存在哪些数字
    var newNums = new Array(nums.length + 1).fill(false);

    var dup = -1, missing = -1;

    for (var i = 0; i < nums.length; i++) {
        // 如果这个数字已经出现过，说明出现重复的数字
        if (newNums[nums[i]]) {
            dup = nums[i];
        }
        // 在新的数组中标记这个数字已经出现过
        newNums[nums[i]] = true;
    }

    for (var i = 1; i < newNums.length; i++) {
        // 没被标记过的数字，说明缺失了某个数字
        if (!newNums[i]) {
            missing = i;
            break;
        }
    }

    return [dup, missing];
};

比如说输入：nums = [1,2,2,4]，算法返回 [2,3]。

其实很容易解决这个问题，先遍历一次数组，用一个哈希表记录每个数字出现的次数，然后遍历一次 [1..N]，看看那个元素重复出现，那个元素没有出现，就 OK 了。

但问题是，这个常规解法需要一个哈希表，也就是 O(N) 的空间复杂度。你看题目给的条件那么巧，在 [1..N] 的几个数字中恰好有一个重复，一个缺失，事出反常必有妖，对吧。

O(N) 的时间复杂度遍历数组是无法避免的，所以我们可以想想办法如何降低空间复杂度，是否可以在 O(1) 的空间复杂度之下找到重复和缺失的元素呢？

本文剩余内容为会员内容，请先购买 网站会员 ，然后 借助 Chrome 插件解锁网页 或者 点这里 跳转小鹅通查看。