之前看的书不行，错误多，题量大但是不精。这次氪了金，换了书，也换了题库，接下来我就以新的算法题为准了。接下来每天就只是总结了，不在是以前写完的代码了，我需要更加注意程序的优化。我现在做的题，有的是LeetCode平台的，有的是《剑指offer》上的，都是python实现。
脑袋时间长不用，今天智商受到了压制。但我依旧相信，自己是最强的！……将来！
题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
例：
输入：[1,2,2,3,3]
输出：1
这题的题目如果没有给说明，那就是一道很开放的题目了。
不是最优解：
一开始我是没有注意到这个说明的后半句，只在意了线性时间复杂度。
头脑简单的我先想到了hash表：用时67ms，内存15.7MB.
class Solution:
def single_number(self, nums:List[int]) -> int:
hashset=set()
for i in nums:
if i not in hashset:
hashset.add(i)
else:
hashset.remove(i)
return list(hashset)[0]
利用集合确定性，遍历链表，新的值进集合，第二次出现就移除它，最后剩下的就是出现一次的值。这个是我脑抽了，列表也可以。。。。这不是最终答案。只能说明我想了这题。。
这种方法的时间复杂度是线性的，只遍历了一次链表，是可以完成找到那一个数的。但是我使用了集合这个额外空间，所以不符合其要求。
后来想用list.count()方法，但是。。。这个方法的效率太低了。用时12000ms+，内存14.5MB.
class Solution:
def singleNumber(self, nums: List[int]) -> int:
for i in nums:
if nums.count(i)==1:
return i
这里我刚刚特地去github看了list源码，回来解释这个问题：
/*[clinic input]
list.count
value: object
/
Return number of occurrences of value.
[clinic start generated code]*/
static PyObject *
list_count(PyListObject *self, PyObject *value)
/*[clinic end generated code: output=b1f5d284205ae714 input=3bdc3a5e6f749565]*/
{
Py_ssize_t count = 0;
Py_ssize_t i;
for (i = 0; i < Py_SIZE(self); i++) {
int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
if (cmp > 0)
count++;
else if (cmp < 0)
return NULL;
}
return PyLong_FromSsize_t(count);
}
python是用c语言写的，所以很容易就能看懂，这个方法是通过循环遍历来返回计数的：for (i = 0; i < Py_SIZE(self); i++),怪不得，每一个元素都要遍历。。。
真闹心，本来以为这个最好了。
我去看了网上大佬的解法，有三种：
1.字典
时间68ms，内存15.4MB
这种方法用的是计数的方法：不是最优解，使用了额外空间——字典
class Solution:
def single_number(self, nums:List[int]) -> int:
dic={x:0 for x in nums}
for x in dic:
dic[x]+=1
for x in dic.item():
if x[1]==1:
return x[0]
说实话这个解法很垃圾。。。，
先新建一个字典{1: 0, 2: 0, 3: 0},初始化每一个数计数为零，遍历列表，统计数字出现的次数，在调用字典的items方法转换为dict_items([(1, 0), (2, 0), (3, 0)])，遍历得到元组第二个值，也就是计数为1的，并返回键值。
用了额外空间，还遍历两次，一次列表，一次字典。
2.数学
用时28ms，内存14.9MB
不是最优解
emmmmm...这个方法是个很快的方法，如果没有要求不能用额外空间，这是最快的。
class Solution:
def single_number(self, nums:List[int]) -> int:
return 2*(sum(set(nums)))-sum(nums)
可以说非常精简了，但还是用到了集合，也是不符合要求。不过相比我的集合，这位大神的厉害多了。
如果列表里的数都是出现两次，那么这个列表的和减掉题中的列表的值，那么得出的便是那个只出现一次的值。
3.异或
52ms，14.2MB
这种方法是最优解，位运算我在学的时候就没学好，现在用上了，就凉凉了。
class Solution:
def single_number(self, nums:List[int]) -> int:
a = 0
for x in nums:
a = a ^ nums
return a
大佬终归是大佬。
利用异或：相同为0，不同为1的特性，出现两次的值会被消为0，入过遇到 了那个唯一的数，没有第二个数可以消除它，最后会被输出。
精髓!!
引申：除了一个数只出现1次，其他数都出现3次：要求相同
class Solution:
def single_number(self, nums:List[int]) -> int:
a, b = 0, 0
for num in nums:
a = ~ b & (a ^ num)
b = ~ a & (b ^ num)
return a
这个就有点复杂了，自己理解下，我现在还解释不好。
我氪金买了正版书……-,我接下来每天的文章就用来总结一天所学了。
加油！辉夜大小姐祝大家——学习进步！
网友评论