leetcode explore 初级算法第五题。原题链接：
题目分析
因为题目不是很长，这里把题目贴出来：
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
题目意思很简单，即找出唯一一个只出现过一次的数字。
参考答案
这个题目首先我们要审清楚题干，题目明确说明了这个列表里只会有一个数字出现一次，因为多个的情况我们不用考虑。对于这种找次数或者是找重复数字的，或者说是针对数字列表进行一些操作的，我们要有一个思维，即先想下排序是否对解题有所帮助。显然这个题目是有的。
因为这个只有一个数字只会出现一次，所以，当列表已经排好序之后，只要找到第一个符合它的下一个数字与它不相等的数字即可。题目要求时间复杂度为线性，而排序时间复杂度为 O(logN)，再循环一遍的时间复杂度为 O(N)，所以总体上时间复杂度是满足题目要求的。
参考代码如下：
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return
nums.sort()
result = nums[0]
pos = 1
result_pos = 0
while pos < len(nums):
if nums[pos] == result:
pos += 1
continue
if pos - result_pos == 1:
break
result = nums[pos]
result_pos = pos
pos += 1
return result
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/1469/viewspace-2824085/ ，如需转载，请注明出处，否则将追究法律责任。
请登录后发表评论
登录
全部评论
