【算法自由之路】算法复杂度、对数器、基本排序、异或与位运算技巧

算法自由之路

算法复杂度

衡量算法常数时间操作次数。忽略常数项，低价项。一般用 O(n) 的形式表示，n 为次数，常见的冒泡排序为 O(n^2)

对数器

最暴力简单的算法，确认正确的不考虑性能的算法即可作为对数器，用来比对优化后的算法。

基本排序算法

冒泡排序，比较排序 O(n^2)

有序数组 二分法寻找元素，寻找最左侧数 。O(log2n)

int mid = L + ((R - L) >> 1)
n * 2 + 1 = (n << 1) | 1
1
2

局部最小（比相邻两端都小）相邻无重复值得数组找到一个根据两端趋势找到一个中间必定存在局部最小值的区间，再次进行二分。、

异或运算 位运算

只记一个点：无进位相加

无额外空间交换两个数的值 ( 相同值，不同空间也可交换，但如果是同一空间的异或交换后为 0) ，尽量别这么写

int a =1;
int b =2;
a = a ^ b; // 1
b = a ^ b; // 2 带入 1 b = a ^ b ^ b = a
a = a ^ b; // 3 带入 2 a = a ^ a ^ b = b
1
2
3
4
5

找奇数次数 一个数在整个数组中出现了奇数次，其他为偶数次。 异或整个数组，最后结果就是这个数 O(n)

取出一个数二进制最右侧的 1

int n = 10;
int x = n & (~n + 1)
1
2

判断某个数某个位为 1

// 比如 0010 判断第二位为 1
int n = 87;
boolen result = (n & 2) != 0
1
2
3

一个数组中出现了两个奇数次的数，找到这两个数 a b

数组全异或后一定为 a ^ b 取最后二进制一位，要么 b 在这一位上为 1 ，要么 a 在这个位上为 1

根据整个性质在整个数组就可以过滤出两组数，一组包含 a，一组包含 b，全异或随便一组得出结果，此结果异或 a ^ b 得出答案。

算 N 二进制的 1 有多少个

int count = 0;

while(N != 0){
	int rightOne = N & (~N + 1);
	count++ ;
	N ^= rightOne;
}
1
2
3
4
5
6
7