python-leetcode-只出现一次的数(我换题库了)

之前看的书不行，错误多，题量大但是不精。这次氪了金，换了书，也换了题库，接下来我就以新的算法题为准了。接下来每天就只是总结了，不在是以前写完的代码了，我需要更加注意程序的优化。我现在做的题，有的是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

这个就有点复杂了，自己理解下，我现在还解释不好。

我氪金买了正版书……^-,我接下来每天的文章就用来总结一天所学了。

加油！辉夜大小姐祝大家——学习进步！