数学专栏课外加餐（二） | 位操作的三个应用实例

我的天，昨天才为老师的加餐点过赞，今天又来一篇干货。谢谢老师，看了这两篇加餐，心里的很多疑惑被解除了。买老师的专栏，值了。 —— 思考题： 需要考虑不同的数量级，分两种情况： 1. 内存能容纳这n个数 方法1：暴力查找，两层循环遍历，时间复杂度为O(n^2)，空间复杂度为O(1) 方法2：用快排先进行排序，然后遍历一次，比较前一个数和后一个数，若相等，则查找完成，时间复杂度O(nlogn)，空间复杂度为O(1) 方法3：利用hash表(或set)，进行一次遍历，同时将遍历到的数放入hash表，放入之前判断hash表是否存在，若存在，则找到了重复的数，时间复杂度为O(n)，空间复杂度为O(n) 方法4：使用位向量，遍历给到的n个数，对于出现的数，将对应位标记为1，如果已经是1则查找成功，时间复杂度为O(n)，空间复杂度为(n)，这种方法类似方法3，虽然渐进的空间复杂度和方法3相同，但是其实小很多很多，毕竟只要用1bit就能表示有或无 2. 内存无法容纳给到的n个数 依然可以用上述方法4来解决，其它的方法有的不能用，有的效率不高。

根据异或的两个特点，任何两个相同的数异或的结果都为0，任何数与0异或都为这个数，因此将所有的数依次异或得到的结果就是除了两个重复数的所有数的异或结果，假设为T。而将1到n依次异或的结果为T^重复数。因此，重复数=T^T^重复数。即:所有数异或的结果再异或1到n所有数异或的结果

看到 Brian Wang 的回答, 您说了正解, 我才想明白: 推到应该是: 原始数据: 1,2...m,m,...n (是否有序对此题不重要) 所有数字: 1,2,...m,...n 因为 x^x = 0 令a = 1^2...^m...^n b = 1^2...^m^m...^n 则有: a^b = (1^2...^m...^n)^(1^2...^m...^n)^m = 0^m = m

思考题：对于有的全部数字进行异或再和 1-n 这 n 个数字进行异或，最终得出的结果就是 m

将所有结果异或再和1到n的不重复结果异或，最后剩余的值就是重复值，真的好神奇，这种异或用法

如果给出的数字不连续，Python中不妨这样使用： ```python from itertools import chain nums_list = [1, 2, 10, 8, 2, 3] nums_set = set(nums_list) start = 0 # 任何数与 0 异或得到自己，所以作为初始值使用 for num in chain(nums_list, nums_set): start = start ^ num print(start) ```

请教老师，用异或交换两个变量值感觉不太懂： 第一步代入第二步时，y已经=x了， 再把第二步代入第三步，此时y的值已经是x，怎么还能利用它把原y值传给x呢？ 感觉还是要临时变量做过渡啊？

假设我们有两个集合{1, 3, 8}和{4, 8}。我们先把这两个集合转为两个 8 位的二进制数，从右往左以 1 到 8 依次来编号。 如果某个数字在集合中，相应的位置 1，否则置 0。那么第一个集合就可以转换为 10000101，第二个集合可以转换为 10001000。 怎么转的？没看懂

不等关系是“最没用”的关系，没有传递性，更没有序性。 如果没有额外空间，直接暴力比较，时间复杂度O(n平方); 如果这n个数字本身是有序的，需要时间复杂度O(n)，排序时间复杂度O(nlog(n))。 如果额外空间充足，在数据聚集度较高甚至连续时，可以使用桶，时间复杂度O(n);如果数据很分散，数据范围远远大于数据量，可以考虑用桶加hash，时间复杂度O(n)，但需要考虑hash碰撞问题。

不太明白，1到n不就是所有数吗，所有数异或所有数不就是0了吗😔😔😔