开个贴记录 leetcode 刷题, 每天刷五道 easy, 刷完后刷 medium, 用 python 和 c++ 做今天第一天, 加油!
题目
原题
- 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?
翻译
给定一个数组, 里面全是整数, 每个数字都重复两遍, 只有一个没有重复, 找到那个不重复的数字
注意: 时间复杂度为线性, 并且不占用额外内存
链接
singular number
方法
我的方法
- from collections import Counter
- class Solution(object):
- def singleNumber(self, nums):
- """
- :type nums: List[int]
- :rtype: int
- """
- return [k for k,v in Counter(nums).items() if v == 1]
- if __name__==__main__:
- print Solution().singleNumber([1,1,2,2,3])
输出结果
3
结果
Wrong Answer
正确答案
- import operator
- class Solution:
- """
- :type nums: List[int]
- :rtype: int
- """
- def singleNumber(self, A):
- return reduce(operator.xor, A)
- if __name__ == __main__:
- print Solution().singleNumber([1, 1, 2, 2, 3])
感想
一开始疑惑为啥错了, 后来放到一起比较后, 发现正确答案输出的是 int 3, 我输出的 list [3], 后来在 return 后面加上了取出这个 list 的值, 结果就对了, 但是运行速度很慢, 对比一下:
- 我的答案: You are here! Your runtime beats 14.20 % of python submissions.
- github 答案: You are here! Your runtime beats 66.96 % of python submissions.
为啥我的答案要慢这么多呢? 留个坑想想
来源: http://www.bubuko.com/infodetail-2517761.html