python之leetcode刷题 006

题目

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,3,2]

输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]

输出: 99

解答

这道题是中等难度的题目,刚开始我一看,哎,这么简单,顺手就写了起来

运行一看也正确,没啥问题,统计数字嘛,以前也遇见过。

可是当我看运行结果我才知道,这道题不是不仅仅是解出来结果就行了。还要考虑时间复杂度。

看一下我的运行结果

执行结果

可以看到只打败了10%的提交者,虽然解决了问题,可耗时太长,显然不是这道题的最好解决方法。

看看大佬的代码

之所以我的代码耗时时间长,是因为每次统计都要遍历一遍列表,大佬的代码只遍历了一次。

再看一个

利用字典来做,时间复杂度最小,耗时28ms,目前来说最好的解决方法。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180812G1AECB00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券