中国制造网官方网站入口网址,物流推广做哪个网站,学ui可以做网站么,休闲食品网站建设策划书【LetMeFly】260.只出现一次的数字 III
力扣题目链接#xff1a;https://leetcode.cn/problems/single-number-iii/
给你一个整数数组 nums#xff0c;其中恰好有两个元素只出现一次#xff0c;其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返…【LetMeFly】260.只出现一次的数字 III
力扣题目链接https://leetcode.cn/problems/single-number-iii/
给你一个整数数组 nums其中恰好有两个元素只出现一次其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。 示例 1
输入nums [1,2,1,3,2,5]
输出[3,5]
解释[5, 3] 也是有效的答案。示例 2
输入nums [-1,0]
输出[-1,0]示例 3
输入nums [0,1]
输出[1,0]提示
2 nums.length 3 * 104-231 nums[i] 231 - 1除两个只出现一次的整数外nums 中的其他数字都出现两次
方法一位运算异或
这道题的本质思路是将所有的数分成两组只出现了一次的数分别分到两组中其余数根据“与单独的数的相似程度”分到这两个组中。这个过程保证了相等的两个数会被分到同一组中。
依据什么将只出现了一次的两个数分到两组中呢我们只需要将所有的数异或异或的结果就是“只出现一次的两个数”的异或结果。这两个数不相等因此这个异或结果一定不为零。
异或结果中为0的位代表两数这一位也相等为1的位代表两数的这一位不同。那么我们就可以根据这个异或结果的“最低一个不为0的位”为依据将所有的数分为两组。这样不相同的两个数一定会被分到不同的组中。
这样对于单个组只有一个只出现了一次的数字 和 出现了两次的数字按照136.只出现一次的数字的方法分别提取出这两个数了。
关于如何求得一个数二进制下第一个不为0的位可以依据lowbit的原理。
时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
class Solution {
public:vectorint singleNumber(vectorint nums) {unsigned int temp 0;for (int t : nums) {temp ^ t;}int mask temp (-temp);vectorint ans(2);for (int t : nums) {ans[(t mask) ! 0] ^ t;}return ans;}
};Python
# from typing import Listclass Solution:def singleNumber(self, nums: List[int]) - List[int]:temp 0for t in nums:temp ^ tmask temp (-temp)ans [0, 0]for t in nums:ans[(t mask) ! 0] ^ treturn ans同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/133872707
