python(leetcode)-136只出现一次的数字
发布于2019-08-07 16:43 阅读(824) 评论(0) 点赞(4) 收藏(0)
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 示例 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)
所属网站分类: 技术文章 > 博客
作者：我好看吗
链接：https://www.pythonheidong.com/blog/article/11642/ab91a3bb3d72ade088d5/
来源：python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力