【leetcode】136. Single Number

题目

Given an array of integers, every element appears twice except for one. Find that single one.

问题陈述：

输入序列中，每个数字重复出现2次，唯有一个数字只出现一次，找到这个只出现一次的数字

题目思路：

hash_table：遍历输入数组，如果hashtable中没有，说明是第一次出现，存到hash table中，如果发现hashtable中已经有了说明是第二次出现，z在hash表中将其删掉，最终hash table中剩下的就是只出现一次的那个数字
bit manipulation：数组中所有数字做异或操作，出现两次的异或之后得0了，最终剩下的就是只出现一次的那个数字。

算法复杂度：O(n)
2比1要快一点,因为1还涉及hash table的查找、插入、删除等操作

代码：

class Solution {//hash_table
public:
    int singleNumber(vector<int>& nums) {
        int len = nums.size();
        unordered_set<int> numset;
    
        for (int i = 0; i < len; i++) {
            if (numset.find(nums[i]) == numset.end()) {//没找到，加入
                numset.insert(nums[i]);
            }
            else//找到了，删除
            {
                numset.erase(nums[i]);
            }
        }
        unordered_set<int>::iterator iter = numset.begin();
        return *iter;
    }
};

class Solution {//逐位异或
public:
    int singleNumber(vector<int>& nums) {
            int len = nums.size();
    int result = 0;
    for (int i = 0; i < len; i++) {
        result ^= nums[i];
    }
    return result;
    }
};

结果

c++ STL中list vector map hashmap 的对比

list

特点：支持快速的插入和删除，但查找费时。

结构：线性双向链表，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。查找元素时需要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。

vector

特点：支持快速的查找，时间复杂度是$O(\log n)$，但是插入费时。

结构：存诸结构是完全二叉检索树，支持快速的查找，但是vector每当增加元素的时候，都需要重新申请新的更大的内存空间，会调用元素的自身的复制构造函数，存在构造成本。在销毁旧内存的时候，会调用析构函数，存在析构成本。

map、set

特点：支持快速的查找，时间复杂度是$O(\log n)$，但是插入费时。

结构：map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，根据key值快速查找记录，查找的复杂度基本是$O(\log n)$，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。

hash_map，hash_set

特点：数据的快速存储和查找，几乎可以看成是常数时间$O(1)$，但是会消耗比较多的内存
结构：基于hash table（哈希表）。使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素。

其插入过程是：
得到key
通过hash函数得到hash值
得到桶号(一般都为hash值对桶数求模)
存放key和value在桶内。

其取值过程是:
得到key
通过hash函数得到hash值
得到桶号(一般都为hash值对桶数求模)
比较桶的内部元素是否与key相等，若都不相等，则没有找到。
取出相等的记录的value。

c++ 中没有hash_map、hash_set标准容器，可以自己定义，重点是做好hash函数的防碰撞。刷题的时候用了STL中的unordered_set,也是基于hashtable的