——————
难点:
时间复杂度为O(n) 空间复杂度为O(1)
复习:前备知识
时空复杂度
O(1)就是最低的时空复杂度了,也就是耗时/耗空间与输入数据大小无关,无论输入数据增大多少倍,耗时/耗空间都不变。
哈希算法就是典型的O(1)时间复杂度,无论数据规模多大,都可以在一次计算后找到目标(不考虑冲突的话)
关于时空复杂度的blog https://blog.csdn.net/u013278314/article/details/82182507 https://blog.csdn.net/zh854663752/article/details/88033093
异或运算符^ 与运算符& 或运算符 |
异或运算符 ^
2 —— 0010
9 —— 1001
2^9 = 1011 = 11
已知两个数字进行异或运算
将 每个数字转换为2进制 然后将每一位按位进行异或运算 异或运算 即 1^1 =0 1^0 =1 0^1=1 0^0=0
a^a=0 a^0=a a^b^c=a^c^b
与运算符 &
负数在计算机进行存储时 是用负数的补码进行存储的 为了方便运算
a&(-a)= (a的二进制 为1的最低位)的二进制(从右到左)
例子:7&-7=1
7——0000 0101
-7——1000 0101 反码——0111 1010 补码——0111 1011
0000 0101
0111 1011 ——》0000 0001
解题
留自己看 可分为两组,一组为与flag相与等于1的[10],另一组为0的[1,2,4,1,4,3,3] 夜深了 回头再写