本文主要是介绍(python版) Leetcode-645. 错误的集合,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
01 题目
链接:https://leetcode-cn.com/problems/set-mismatch
集合 S 包含从1到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个元素复制了成了集合里面的另外一个元素的值,导致集合丢失了一个整数并且有一个元素重复。
给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。
示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
注意:
给定数组的长度范围是 [2, 10000]。
给定的数组是无序的。
02 解析
^是位异或运算,对应的二进制位同为du0或同为1 结果为0 。(00为0,11为0,01和10为1)
比如 a = 2 b =1 对应的二进制为a = 10 b=01 ,进行^异或操作
所以 a^=b 即 a= a^b 也就是 10^01 = 11. 故a变成11
【这个总结的不错 https://leetcode-cn.com/problems/set-mismatch/solution/zhi-chu-xian-yi-ci-de-shu-xi-lie-wei-yun-suan-by-f/】
重复的数a, 丢失的数b
缺少的那个数b,由两个集合(true, 和nums)的差集得到
两个集合一块做^, 得到a ^ b的结果c, 已知b, c, 可以得到c ^ b =a
a ^ b = c =====》 c ^ b = a
时间复杂度: O(N), 空间复杂度: O(1)
03 代码
class Solution:def findErrorNums(self, nums: List[int]) -> List[int]:res = 0length = len(nums)err = sum(nums) - sum(set(nums)) # 重复for n in nums:res ^= nfor i in range(1, length+1):res ^= irep = err ^ resreturn [err, rep]
https://leetcode-cn.com/problems/set-mismatch/solution/zhi-guan-yi-dong-de-wei-yun-suan-by-clark-12/
Line 8-12:是什么意思?
这篇关于(python版) Leetcode-645. 错误的集合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!