简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
一、写在前面
LeetCode 第十六和十七题螺旋矩阵传输门：LeetCode016 & 17 :螺旋矩阵 & 螺旋矩阵Ⅱ（尾部有autopep8配置使用）
今天给大家分享的是老表刷LeetCode 第十八篇： 只出现一次的数，为面试而生，期待你的加入。
“Use the utility in the API is recommended in the project. But if you use it in an interview, you will definitely fail .”
二、今日题目
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
实例
示例 1: 输入: [2,2,1] 输出: 1 示例 2: 输入: [4,1,2,1,2] 输出: 4
三、 分析
这个题目，看着还是比较简单的，列表里只有一个元素是单独存在的，其他元素都是成对存在（着实虐狗啊），那么怎么把这个狗找出来了，我最开始想到了之前用到的一个列表元素计数的模块collections的Counter方法，返回一个字典，key是元素值，vaule是该元素出现的次数，我直接判断vaule是不是等于一就好了，然后返回对应的key值，这样就有了方法一，当然还有其他方法，具体看下面的解题部分，大概思路如下：
老表亲自手写
四、解题
1. 第一眼想到的,Counter函数：
表面上看，时间复杂度：O(n)
空间复杂度：O(1)
(1)代码
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ # 导入计数模块 from collections import Counter count = Counter(nums) # 返回的是个字典对象 # key : 原列表元素 # vaules : 对应元素出现次数 for k, v in count.items(): # 遍历列表找到答案 if v == 1: return k
(2)提交结果
测试数据：16组
运行时间：268ms
击败人百分比:9.56%
2.根据规律之一：
根据题目，所有元素只有一个元素单个存在（下面把它称为目标元素），其他元素均成对存在，所以易推测元素个数为奇数个，并且如果把列表排序后，目标元素的索引下标必然为偶数（列表索引从0开始，排序后其他相同元素必然是0，1，在前面或者后面可能是目标元素，所以目标元素的索引必然为偶数），那么我们只需要用偶数项的和减去奇数项的和即可找出目标元素值。
时间复杂度：O(n)
空间复杂度：O(1)
(1)代码
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ # 排序 nums.sort() temp = nums[0] # for循环遍历，作差，遍历一半即可 for i in range(len(nums)//2): # 偶数下标减奇数下标，并计算差的和 temp = temp - nums[2*i+1] + nums[2*i+2] return temp
(2)提交结果
测试数据：16组
运行时间：36ms
击败人百分比:48.59%
额外知识：
十大排序算法，图片来自互联网博客
3.根据规律之二：
我们现在要做的就是开心连连看游戏，相同的数据应该连接后消失，等所有相同元素都已经被连接消失后，自然就只剩下我们要找的目标元素了，根据数学逻辑，这里的连连看-消失的功能我们可以用逻辑异或来实现，相同的元素异或，结果为0，不同的元素异或按位进行异或操作（二进制），任何元素与0进行异或结果为它自己，根据思想实现代码如下。
时间复杂度：O(n)
空间复杂度：O(1)
(1)代码
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ flag = 0 # 起始数 for i in range(len(nums)): # 异或找不同元素 ^ 为Python里的异或标识 flag = flag ^ nums[i] return flag
(2)运行结果
测试数据：16组
运行时间：32ms
击败人百分比:70.82%
额外知识
图片来自菜鸟教程
五、疑惑
今日分享：如果你处于和我一样“比上不足，比下有余”的地方，我建议你两点：
1、承认。
有人比我们优秀是正常的，没有人比我们优秀这才是坏事，如果你发现，你周围的人都不如你优秀，那说明，你现在的环境已经不适合你发展了，当然你可以跳出当前环境或者接触新环境带动当前环境（前者是技术人，后者是领导者）
2、做自己。
完全没必要去和不优秀的人比较，也没必要和特别优秀的人较劲，做好自己，人生漫漫长路，你得一点一点积累，不因小事而停顿，不因大事而搓返。
六、结语
思想很复杂，
实现很有趣，
只要不放弃，
终有成名日。
---《老表打油诗》
我决定了，继续开展留言打卡活动
