bilibili《算法与数据结构》左神课程笔记

需要理解，经过大量的练习，很难练。记忆性的东西没那么重要，重要的是思维。是绝对代码能力、耐心努力、智力程度的证明。
系统的开销如果很大，会不实用，留给用户的就很少。

时间复杂度

常数操作：
+ - * /位运算。跟数据量无关，是个固定时间的东西。看一眼（寻址）、比较、交换操作（swap），
单链表：链表结构是一个串着另外一个，在内存里指的是比较乱的，尽管在逻辑上是从左往右的。因此list.get(i)不是常数操作。

0, n-1找最小值。在常数操作数量级的表达式中，不要低阶项，只要高阶项，且忽略高阶项的系数。比如：常数操作aN²+bN+C，时间复杂度为O (N²）。估计的是数学上的上限。

O最差数据状况下的表现
θ平均数据状况下的表现（没啥用）
Ω最优数据状况下的表现（没啥用）

额外空间复杂度

如果只需要有限几个变量就可以完成算法流程，额外空间复杂度O（1）
如果需要额外开辟一个数组，并且与原属于等规模，额外空间复杂度O（N）

认识时间复杂度
常数时间的操作
一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
时间复杂度为一个算法流程中，常数操作数量的一个指标。常用O(读作big O)来表示。具体
来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，
进而总结出常数操作数量的表达式。
在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N)，那
么时间复杂度为O(f(N))。
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行
时间，也就是“常数项时间”。

位运算

异或运算（也可以理解为无进位相加）：

相同为0，不同为1
性质：
1、0^N =N， N^N = 0
2、满足交换律和结合律，同一批数的异或结果是一样的。(最终结果只与每个位置1的个数有关，而与异或顺序无关)

请不要用这种方法：

int  a = 17
int b = 23
a = a^b
b = a^b  # b = a^b^b = a^0 = a
a = a^b  # a^b^a = 0^b = b

前提：a与b在内存中是独立的，不在同一个内存位置。否则会被洗成0的。

public static void main(String[], args){int a = 10int b = 10a = a^bb = a^ba = a^b
}

题目：只出现一次的数字

题目：

第一问：数组中只有一种数出现了奇数次，其他所有数都出现了偶数次。如何找到那个数？
.
第二问：数组中只有两种数出现了奇数次，其他所有数都出现了偶数次。如何找到两种数？
要求时间复杂度O（N），空间复杂度O（1）

不能用等差数列，否则时间复杂度是O（N²）
异或用起来！消消乐原理

解：
第一问：
JAVA代码：

int eor = 0
# 把eor从头异或到尾
for(int cur : eor){eor ^= cur;
}
system.out.println(eor);

python3代码：

class Solution:
def singleNumber(self, nums: List[int]) -> int:eor = 0for i in nums:eor ^= ireturn eor

第二问：
解析：

int eor = 0
# eor从头异或到尾
# 全部异或之后，eor ！= 0，表示eor = a^b
# 假设eor在第8位上不是0，是1，说明a与b在第8位上一定是不一样的。# 再准备一个变量：eor'，只异或在第8位是1的情况（是0的情况直接跳过不看）
# 这样可以把整个数组分为两类：第8位是1的数，第8位是0的数
# a 与 b只会占一侧
# 这样就可以得出a或b
eor' = a or b  
eor ^ eor' = a^b^(a or b) = b or a # 即可得出一个数

JAVA代码：

位运算是最快的，比算术运算快多了

public static void printOddTimesNum2(int[] arr){int eor = 0;// 下面代码等同于// for(int i = 0;i<arr.length;i++){//	eor ^= arr[i]//}for(int curNum : arr){eor ^= curNum;}// eor = a^b// eor != 0 ，because a!=b，是两个不同的数// eor 必然有一个位置是1int rightone = eor & (~eor + 1); # 提取出最右的1（常规操作，记住）// eor：101011100// ~eor：010100011// ~eor+1：010100100// eor & (~eor+1)：000000100int onlyone = 0  // eor'for(int cur : arr){if ((cur & rightone) == 1){ // 确保参与运算的是数组中的1onlyone ^= cur;  // a or b}System.out.println(onlyone + " " + (eor ^ onlyone))  // 一个是onlyone，另一个是eor^onlyone的结果}}