python(leetcode)-136只出现一次的数字

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python(leetcode)-136只出现一次的数字，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1799字，纯文字阅读大概需要3分钟。

内容图文

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

先说自己的思路 这题和217存在重复问题相似 这题找数组中只有一次的数字 而存在重复问题是找出现两次的数字 

所以我先排序 然后以2为间隔两两进行对比 是否相同 如果不同则return值 如果倒数第二个之前都是相同的 则return 最后一个值

上代码（通过）

 1 class Solution:
 2     def singleNumber(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: int
 6         """
 7         nums.sort()
 8         for i in range(0,len(nums),2): #以2为间隔 两两对比
 9             if(i==(len(nums)-1)):      #倒数第二个之前都相同 返回最后一个值
10                 return nums[i]
11             else:
12                 if(nums[i+1]!=nums[i]):
13                     return nums[i]
14 if __name__=="__main__":
15     s=Solution()
16     nums=[5,3,5,6,7,3,6]
17     print(s.singleNumber(nums))

运行时间为60ms 只击败49%的用户

代码虽然通过检测 但是分析过程发现 首先的排序时间复杂度就为O(nlogn) 并不是线性的 所以虽然通过测试但不是最优

第二种思路 （看评论区大佬写的） 利用按位异或运算符 进行操作

 1 class Solution:
 2     def singleNumber(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: int
 6         """
 7         a = 0
 8         for num in nums:
 9             a = a ^ num
10         return a
11 
12 if __name__=="__main__":
13     s=Solution()
14     nums=[5,3,5,6,7,3,6]
15     print(s.singleNumber(nums))

运行代码 48ms 击败99.8%的用户

会发现效率提升其实很明显 虽然代码相对简单 4行解决 但是可能理解起来较难

分析一下亦或运算符^ :当两对应的二进位相异时，结果为1。

首先这是对两个二进制数字进行操作 如果对应位相异为1否则为0

a^a=0
0^a=a
a^b=b^a
a^a^b=b
a^b^c=(a^b)^c=a^(b^c)

内容总结

以上是互联网集市为您收集整理的python(leetcode)-136只出现一次的数字全部内容，希望文章能够帮你解决python(leetcode)-136只出现一次的数字所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端