约 1053 字大约 4 分钟数学位运算

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) 的空间复杂度之下找到重复和缺失的元素呢?
共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释