数据结构精品课 已更新到 V2.1, 手把手刷二叉树系列课程 上线。
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 和刷题全家桶:
共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释