首页 > 代码库 > Single Number | LeetCode OJ 解题报告
Single Number | LeetCode OJ 解题报告
题目网址：https://oj.leetcode.com/problems/single-number/
题目描述：
Given an 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?
找一个出现次数仅为一次的数，O(n)时间
题目解答：
初步的想法就是把array排序，然后从前往后配对，遇见不一样的就是第一个数是出现一次的，考虑边界条件（array长度是1或者最后一个数是要找的数）
def singleNumber(self, A): A.sort() if len(A) == 1: return A[0] for i in A: if i%2 == 1: if A[i] != A[i-1]: return A[i-1] else: pass print "hey bitch:" + "A[" + str(i) + "] = " + str(A[i]) + "\n" elif i == len(A): return A[len(A)]
很可惜这玩意超时了。然后我就想了，list是个超级低效的数据结构，何不用dict，于是：
#A.sort() D = {} for i in A: if i not in D: D[i] = 1 else: D[i] = D[i]+1 for i in D: if D[i] == 1: return i空间、时间复杂度O(n),其实sort不sort差不多,但是sort的时间复杂度为O(nlogn)。但是，题目里说了，怎么才能少用或者不用memory?于是:
A.sort() while len(A) != 1: a = A.pop() b = A.pop() if a == b: pass else: return a return A[0]
用了O(1)空间，但是时间又涨到O(nlogn)，绞尽脑汁，想不出来啊。于是翻了翻评论，原来还有位运算这回事儿：
if len(A) == 1: return A[0] else: for a in A[1:]: A[0] = a^A[0] return A[0]
这才是真正满足题目要求的解，虽然上面的代码都过了吧
Single Number | LeetCode OJ 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。