1.何为常数时间的操作？
2.如何确定算法流程的时间复杂度？
3.如何确定算法流程的总操作数量与样本数量之间的表达式关系？
4.常见的时间复杂度
5.认识异或运算
6.为什么要手撸数据结构算法？
1.何为常数时间的操作？
如果一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定时间。称遮掩你的操作为常数时间的操作
例如，数组取数，数组下标取数，是取固定地址的偏移量取值，取数耗时T和这个数的大小，数组下标的大小无关。
常见的常数时间操作
- 常见的算术运算（+ , - , * , / , %等）
- 常见的位运算（>> , >>> , << , | , & , ^ 等）
- 赋值，比较，自增，自减操作等
- 数组寻址操作
总之：执行时间固定的操作都是常数时间操作。
反之：执行时间不固定的操作都不是常数时间操作。
1.如何确定算法流程的时间复杂度？
当完成了表达式的建立，只要把最高阶项留下即。低阶项都去掉，高阶的系数也去掉。
记作：O(忽略掉系数的高阶项)
3.如何确定算法流程的总操作数量与样本数量之间的表达式关系？
1，想想该算法流程所处理的数据状况，要按照最差情况来。
2，把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数的操作。
3，如果数据量为N，看看基本动作的数量与N是什么关系。
4.常见的时间复杂度
排名从好到差：
- O(1)
- O(logN)
- O(N)
- O(N * logN)
- O(N^2) O(N^3) O(N^4) O(N^5) ... O(N^k)
- O(2^N) O(3^N) O(4^N) O(5^N) O(k^N)
- O(N!)
5.认识异或运算
同或运算：--
异或运算：可以看作是无进位的加法器。满足交换律和结合律
案例1：快速找出一个数组中个数为奇数的那个数，并返回他
/**
* 快速找出一个数组中个数为奇数的那个数，并返回。（只有一个奇数）
* @author Tara
* @implNote
*/
public class Pra4 {
public static void main(String[] args) {
int[] arr = new int[]{5,2,3,4,5,2,3,4,5,6,2,3,4,5,1,2,3,4,5,6,4,4,2,23,4,2,1,23,4};
int a = 0;
for (int i=0;i<arr.length;i++){
a^=arr[i];
}
System.out.println(a);
}
}
案例2：快速取出一个数二进制最后一位1 ： N & （~N + 1）
/**
* 快速取出一个数二进制最后一位1 ： N & （~N + 1），去除的数为1，2，4，8，16，32，64，128，256，。。。。
* 例如 24 <==>11000,要取出1000（十进制8）,
* @author Tara
* @implNote
*/
public class Pra5 {
public static void main(String[] args) {
int a = 24;
System.out.println(a & (~a+1));
for (int i = 0; i < 500; i++) {
int b = i;
System.out.print((b & (~b+1))+",");
}
}
}
案例3：一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数？
/**
* 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数？
* @author Tara
* @implNote
*/
public class Pra6 {
public static void main(String[] args) {
int arr[] = new int[]{0,1,2,3,4,5,1,2,3,4,5,0,2,4,5,6};
printOddNums(arr);
}
private static void printOddNums(int[] arr) {
// 所有数做异或操作
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor^=arr[i];
}
// 去除num左右侧的1
int rightOne = eor & (~eor+1);
for (int i = 0; i < arr.length; i++) {
if ((arr[i] & rightOne) == rightOne){
rightOne^=arr[i];
}
}
System.out.println("第一个数是"+rightOne +"第二个数是"+(eor^rightOne));
}
}
案例4：将10进制数转成二进制，找出其中有多少个1
/**
* 将10进制数转成二进制，找出其中有多少个1
* @author Tara
* @implNote
*/
public class Pra7 {
public static void main(String[] args) {
int N = 13257423;
findCounts(N);
}
private static void findCounts(int n) {
// 计数
int count = 0;
//每次都抹去最后一个1
while (n >0){
int rithtOne = n & (~n +1);
//抹掉最后一个1
n^=rithtOne;
//思考，为什么抹掉最后一个1，用异或，不用-rightOne ??? 答：因为如果N为负数的时候，会出问题。
count++;
}
System.out.println("有"+count);
}
}
6.为什么要手撸数据结构算法？
1.算法与语言无关；
2.语言提供的api是有限的，当有新功能api不提供就需要改写
3.任何软件工具的底层都是基本的算法与数据结构，这个是绕不过去了。
