LeetCode 面试题56-l .数组中数字出现的次数

——————

难点:

  时间复杂度为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 

    https://blog.csdn.net/littesss/article/details/70495810?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1

解题

留自己看 可分为两组,一组为与flag相与等于1的[10],另一组为0的[1,2,4,1,4,3,3] 夜深了 回头再写

  

                

   

原文地址:https://www.cnblogs.com/patterndream/p/12806089.html