门户网站建设价格,免费网站制作软件的app,网站建设公司咨询电话,天河建网站136.只出现一次的数字
给你一个 非空 整数数组 nums #xff0c;除了某个元素只出现一次以外#xff0c;其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题#xff0c;且该算法只使用常量额外空间 示例 1 #xf…136.只出现一次的数字
给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间 示例 1 输入nums [2,2,1]
输出1示例 2 输入nums [4,1,2,1,2]
输出4示例 3 输入nums [1]
输出1本题采用位运算进行解答首先介绍一下异或运算
不同为1相同为0
0^11
1^100与任何数进行异或等于任何数。任何数与本身运算等于0异或满足交换律和集合率
0^NN
N^N0
A^BB^A
A^(B^C)(A^B)^C
本题求出现一次的数出现偶数次的数异或为0最后0与出现一次的数异或则等于该数。下面是程序代码
def singlenumber(nums):er0for i in range(0,len(nums)):erer^nums[i]return er 260.只出现一次的数字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] 这一题是求只出现一次的两个数那么我们 应该如何去求解首先如果还是按上题思路我们假定一个er为0只出现一次的数分别为a,b对数组中的每个元素都进行异或那么最终得到的结果将是era^b无法求求出两个元素。
如何求解首先两个元素是不一样的数字所以他们两个异或结果不会是0也就是era^b!0
这个时候我们可以将整个数组分为两部分取er最右边为1的二进制数也就是a和b在这个位置不一样我们可以根据这个数将其余出现两次的元素分为两部分一部分是该位置元素为1一部分是该位置元素为0。我们分别对这两部分数求异或即可得到对应的出现一次的数。 def singleNumber(nums):er0for i in range(0,len(nums)):erer^nums[i]#求解二进制最右边为1rightoneer(~er1) #对原二进制数求反加1与原二进制进行与运算er10for i in range(0,len(nums)):if(rightonenums[i]0):er1^nums[i]aer1^erreturn [a,er1]
