本文共 1719 字，大约阅读时间需要 5 分钟。

评估算法优劣的核心指标：

1、时间复杂度

就是在流程中发生多少次常数时间操作

2、空间复杂度

输入输出的空间不算

3、常数时间的操作：

如果一个操作的执行时间不以具体数据量为转移，每次执行时间都是固定时间，这样的操作为常数时间的操作。

例如：

• 常见的算术运算
• 常见的位运算（>> 带符号右移，最高位用符号位补足，>>> 不带符号位右移，最高位都用0补足）
• 赋值、比较、自增、自减操作等
• 数组寻址操作

如何确定算法流程的总操作数量与样本之间的表达式关系？

1、想象该算法流程所处理的数据状况，要按最差情况来

2、把整个流程彻底拆分为一个个基本动作，保证每个动作都是非常数时间的操作

3、如果数据量为N，看看基本动作的数量和N是什么关系

常见的位运算

N * 2 = N<<1

N * 2 + 1 = (N<<1) | 1

(L + R) / 2 = L + ((R - L) >> 1)

异或运算：相同为0不同为1

同或运算：相同为1不同为0

异或运算记为无进位相加

异或运算的性质：

1） 0^N == N   N^N == 0

2) 满足交换律和结合律，同样的数字以不同顺序异或结果都是一样的

题目1：

如何在不申请额外的空间交换两个变量的值？

根据上述的异或运算的第一条，可以得出交换过程是：

1、a = a ^ b;  a = 甲 ^ 乙， b = 乙；

2、b = a ^ b;  a = 甲 ^ 乙,  b = 甲 ^ 乙 ^ 乙 = 甲

3、a = a ^ b;  a = 甲 ^ 乙 ^ 甲 = 乙，b = 甲

但是必须保证两个数字指向的内存是不一样的

题目2：

一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数？

把数组里的数全部异或起来，最后得出的值就是出现奇数次的数，可以先定义一个变量为0，这样免去判断数组越界

题目3：

怎么把一个int类型的数，提取出最右侧的1来？

N & (~N + 1)  ：N 与 N 取反加1

例如：

N =    0000 1101 0100 00

~N =       1111 0010 1011 11

~N + 1 =  1111 0010 1100 00

N & (~N + 1)  = 0000 0000 0100 00

题目4：

一个数组中有两种数出现了奇数次，其他都出现了偶数次，怎么找到并打印这两种数？

假设出现奇数次的这两个数是a和b，所有数字都异或起来的值就是c=a^b，c 的某一位是0，说明a和b在这一位上的值相同，某一位为1，说明a和b在这一位上的值不同

任选一个值是1的位置d，去异或数组中所有位置d为1的数，结果就是其中一个奇数的值，再去异或c，就得到了另一个奇数的值

位置d一般找最右侧为1的位置是最快的

public void printOddTimesNum2(int [] arr){  int eor = 0;  for (int i = 0; i < arr.length; i++){    eor ^= arr[i];  }  int rightOne = eor & (~eor + 1);  int onlyOne = 0;  for (int i = 0; i < arr.length; i ++){    if ((arr[i] & rightOne) == rightOne){      onlyOne ^= arr[i];    }  }  System.out.println(onlyOne + " " + (onlyOne ^ eor));}

题目5:

给出一个整数N，统计二进制中1出现的次数

public int bit1counts(int N){  int count = 0;  // 兼容负数，只能用不等于0来做判断  while (N != 0){    int rightOne = N & ((~N) + 1);    // 不需要每次判断,rightOne是否为0，因为只有n=0时，rightOne才会为0    count ++;    N ^= rightOne;  }}

这样比从头到尾统计32次要快

转载地址：https://blog.csdn.net/yshuoo/article/details/115731036 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！