如何同时寻找缺失和重复的元素
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 645. Set Mismatch | 🟢 |
Today, let's discuss a problem that seems simple but is quite clever: finding the missing and duplicate elements. I've written about a similar problem in a previous article Common Bit Manipulations, but the techniques used in this problem are different from the last one.
This is LeetCode problem #645 "Set Mismatch." Here's a description of the problem:
Given an array nums of length N, which originally contains the elements [1..N] in no particular order, some errors have occurred. One element in nums is duplicated, which simultaneously causes another element to be missing. Your task is to write an algorithm to find the values of the duplicate and missing elements in nums.
// Return two numbers, which are {dup, missing}
int[] findErrorNums(int[] nums);// Return two numbers, which are {dup, missing}
vector<int> findErrorNums(vector<int>& nums);# Return two numbers, which are {dup, missing}
def findErrorNums(nums: List[int]) -> List[int]:// Return two numbers, which are {dup, missing}
func findErrorNums(nums []int) []int {}// Return two numbers, which are {dup, missing}
var findErrorNums = function(nums) {}For example, given the input: nums = [1,2,2,4], the algorithm returns [2,3].
This problem is actually quite easy to solve. First, traverse the array once and use a hash table to record the frequency of each number. Then, traverse the range [1..N] to identify which element is duplicated and which is missing. That's it.
However, the issue is that this conventional approach requires a hash table, which means an O(N) space complexity. Given the clever conditions provided in the problem—exactly one duplicate and one missing number in the range [1..N]—something unusual must be going on, right?
An O(N) time complexity to traverse the array is unavoidable, so let's think about how to reduce the space complexity. Is it possible to find the duplicate and missing elements with O(1) space complexity?