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) 的空间复杂度之下找到重复和缺失的元素呢？

思路分析

这个问题的特点是，每个元素和数组索引有一定的对应关系。

我们现在自己改造下问题，暂且将 nums 中的元素变为 [0..N-1]，这样每个元素就和一个数组索引完全对应了，这样方便理解一些。

如果说 nums 中不存在重复元素和缺失元素，那么每个元素就和唯一一个索引值对应，对吧？

现在的问题是，有一个元素重复了，同时导致一个元素缺失了，这会产生什么现象呢？会导致有两个元素对应到了同一个索引，而且会有一个索引没有元素对应过去。

那么，如果我能够通过某些方法，找到这个重复对应的索引，不就是找到了那个重复元素么？找到那个没有元素对应的索引，不就是找到了那个缺失的元素了么？

那么，如何不使用额外空间判断某个索引有多少个元素对应呢？这就是这个问题的精妙之处了：

通过将每个索引对应的元素变成负数，以表示这个索引被对应过一次了，算法过程如下 GIF 所示：

如果出现重复元素 4，直观结果就是，索引 4 所对应的元素已经是负数了：

对于缺失元素 3，直观结果就是，索引 3 所对应的元素是正数：

对于这个现象，我们就可以翻译成代码了：

int[] findErrorNums(int[] nums) {
    int n = nums.length;
    int dup = -1;
    for (int i = 0; i < n; i++) {
        int index = Math.abs(nums[i]);
        // nums[index] 小于 0 则说明重复访问
        if (nums[index] < 0)
            dup = Math.abs(nums[i]);
        else
            nums[index] *= -1;
    }

    int missing = -1;
    for (int i = 0; i < n; i++)
        // nums[i] 大于 0 则说明没有访问
        if (nums[i] > 0)
            missing = i;
    
    return new int[]{dup, missing};
}

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

vector<int> findErrorNums(vector<int>& nums) {
    int n = nums.size();
    int dup = -1;
    for (int i = 0; i < n; i++) {
        int index = abs(nums[i]);
        // nums[index] 小于 0 则说明重复访问
        if (nums[index - 1] < 0)
            dup = abs(nums[i]);
        else
            nums[index - 1] *= -1;
    }

    int missing = -1;
    for (int i = 0; i < n; i++)
        // nums[i] 大于 0 则说明没有访问
        if (nums[i] > 0)
            missing = i+1;
    
    return vector<int>({dup, missing});
}

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

def findErrorNums(nums: List[int]) -> List[int]:
    n = len(nums)
    dup = -1
    # 访问每个数字并记录是否访问过
    for i in range(n):
        index = abs(nums[i])
        # 如果修改后的nums[index]为负数，则说明此数字已经被访问过，说明为重复数字
        if nums[index] < 0:
            dup = abs(nums[i])
        else:
            nums[index] *= -1  # 通过将此处数字乘以 -1 的方式记录是否访问过此处数字

    missing = -1
    # 查找没有访问的数字，其下标即为缺失数字
    for i in range(n):
        if nums[i] > 0:
            missing = i

    return [dup, missing]

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

// findErrorNums 解决方案
func findErrorNums(nums []int) []int {
    n := len(nums)
    dup := -1
    for i := 0; i < n; i++ {
        index := abs(nums[i])
        // 如果 nums[index] 小于 0，则说明 index 已经出现过，因此该数字是重复数字
        if nums[index] < 0 {
            dup = abs(nums[i])
        } else {
            nums[index] *= -1
        }
    }

    missing := -1
    for i := 0; i < n; i++ {
        // 如果 nums[i] 大于 0，则说明数字 i 没有出现过
        if nums[i] > 0 {
            missing = i
        }
    }

    return []int{dup, missing}
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

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

var findErrorNums = function(nums) {
    var n = nums.length;
    var dup = -1;
    for (var i = 0; i < n; i++) {
        var index = Math.abs(nums[i]);
        // nums[index] 小于 0 则说明重复访问
        if (nums[index] < 0)
            dup = Math.abs(nums[i]);
        else
            nums[index] *= -1;
    }

    var missing = -1;
    for (var i = 0; i < n; i++)
        // nums[i] 大于 0 则说明没有访问
        if (nums[i] > 0)
            missing = i;
    
    return [dup, missing];
}

这个问题就基本解决了，别忘了我们刚才为了方便分析，假设元素是 [0..N-1]，但题目要求是 [1..N]，所以只要简单修改两处地方即可得到原题的答案：

int[] findErrorNums(int[] nums) {
    int n = nums.length;
    int dup = -1;
    for (int i = 0; i < n; i++) {
        // 现在的元素是从 1 开始的
        int index = Math.abs(nums[i]) - 1;
        if (nums[index] < 0)
            dup = Math.abs(nums[i]);
        else
            nums[index] *= -1;
    }

    int missing = -1;
    for (int i = 0; i < n; i++)
        if (nums[i] > 0)
            // 将索引转换成元素
            missing = i + 1;

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

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

vector<int> findErrorNums(vector<int>& nums) {
    int n = nums.size();
    int dup = -1;
    for (int i = 0; i < n; i++) {
        // 现在的元素是从 1 开始的
        int index = abs(nums[i]) - 1;
        if (nums[index] < 0)
            dup = abs(nums[i]);
        else
            nums[index] *= -1;
    }

    int missing = -1;
    for (int i = 0; i < n; i++)
        if (nums[i] > 0)
            // 将索引转换成元素
            missing = i + 1;

    return vector<int>{dup, missing};
}

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

def findErrorNums(nums: List[int]) -> List[int]:
    n = len(nums)
    dup = -1
    for i in range(n):
        # 现在的元素是从 1 开始的
        index = abs(nums[i]) - 1
        if nums[index] < 0:
            dup = abs(nums[i])
        else:
            nums[index] *= -1

    missing = -1
    for i in range(n):
        if nums[i] > 0:
            # 将索引转换成元素
            missing = i + 1

    return [dup, missing]

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

// findErrorNums 找出重复的数和缺失的数
func findErrorNums(nums []int) []int {
    n := len(nums)
    dup := -1
    for i := 0; i < n; i++ {
        // 现在的元素是从 1 开始的
        index := abs(nums[i]) - 1
        if nums[index] < 0 {
            dup = abs(nums[i])
        } else {
            nums[index] *= -1
        }
    }

    missing := -1
    for i := 0; i < n; i++ {
        if nums[i] > 0 {
            // 将索引转换成元素
            missing = i + 1
        }
    }

    return []int{dup, missing}
}

// abs 取绝对值
func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

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

var findErrorNums = function(nums) {
    var n = nums.length;
    var dup = -1;
    for (var i = 0; i < n; i++) {
        // 现在的元素是从 1 开始的
        var index = Math.abs(nums[i]) - 1;
        if (nums[index] < 0)
            dup = Math.abs(nums[i]);
        else
            nums[index] *= -1;
    }

    var missing = -1;
    for (var i = 0; i < n; i++)
        if (nums[i] > 0)
            // 将索引转换成元素
            missing = i + 1;

    return [dup, missing];
};

🌈 代码可视化动画 🌈

其实，元素从 1 开始是有道理的，也必须从一个非零数开始。因为如果元素从 0 开始，那么 0 的相反数还是自己，所以如果数字 0 出现了重复或者缺失，算法就无法判断 0 是否被访问过。我们之前的假设只是为了简化题目，更通俗易懂。

最后总结

对于这种数组问题，关键点在于元素和索引是成对儿出现的，常用的方法是排序、异或、映射。

映射的思路就是我们刚才的分析，将每个索引和元素映射起来，通过正负号记录某个元素是否被映射。

排序的方法也很好理解，对于这个问题，可以想象如果元素都被从小到大排序，如果发现索引对应的元素如果不相符，就可以找到重复和缺失的元素。

异或运算也是常用的，因为异或性质 a ^ a = 0, a ^ 0 = a，如果将索引和元素同时异或，就可以消除成对儿的索引和元素，留下的就是重复或者缺失的元素。可以看看前文常用的位运算，介绍过这种方法。

引用本文的题目

安装我的 Chrome 刷题插件点开下列题目可直接查看解题思路：

LeetCode	力扣
442. Find All Duplicates in an Array	442. 数组中重复的数据
448. Find All Numbers Disappeared in an Array	448. 找到所有数组中消失的数字

＿＿＿＿＿＿＿＿＿＿＿＿＿

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释