数据结构与算法基础到高级，直击BTAJ，刷爆Letcode

🎄前序补充
- 🍕异或
- 🍔对数器
🎄时间、空间复杂度
- 🍟空间复杂度基本概念
- 🌭时间复杂度基本概念
- 🍿基本的排序算法的时间复杂度
- - ✨冒泡排序/起泡排序(Bubble Sort)
  - ✨插入排序（Insertion Sort）
- 🧂递归行为的时间复杂度
- - ✨二分法
  - ✨归并排序
  - ✨荷兰国旗问题
  - ✨快速排序

🎉🎉分享DS学习笔记，不定时更新，内容对标左神全套教学~

笔记并非按照内容类型整理，而是根据一定的逻辑关系组织而成。如有问题可🔖留言评论区或📣私信哦~

🎄前序补充

🍕异或

异或结果与顺序无关

X^YZ = Y^ZX = X^ZY

应用

交换两个数的值

//a = X,b = Y
//使用前提：a、b在内存中是两块独立的空间（例如，将数组中i与j位置互换，若i=j，会将i位置值处理为0）
public static void exchange(int a,int b){a = a^b;	//a = X^Y , b = Yb = a^b;	//a = X^Y , b = X^Y^Y = X^0 = Xa = a^b;	//a = X^Y^X = Y^0 = Y , b = X
}

一堆数字中，X出现了奇数次，其它数字出现了偶数次，求X

//将所有数值取异或，偶数次数字两两异或为0，最终剩余X^0 = X
//X^Y^V^Z^X^X^V^T^Y^T^Z = (Y^Y)^(V^V)^(Z^Z)^(T^T)^(X^X)^X = 0^X = X
public static void printOddTimesNum(int[] arr){int eor = 0;for(int cur:arr){eor ^= cur;}System.out.println(eor)
}

一堆数字中，X,Y（X、Y是不同的两个数）出现了奇数次，其它数字出现了偶数次，求X,Y

//将所有数值取异或，结果为eor = X^Y,由于X！=Y，因此eor != 0,即eor必然有一个位置为1(代表X、Y此位置一个为1，一个为0)。
//将此位置为1的数异或，得到X or Y中的一个数;将eor与该数异或，得到另一个数
public static void printOddTimesNum(int[] arr){int eor = 0,onlyOne = 0;for(int curNum:arr){eor ^= curNum;}//(与自身取反+1再相与)提取出最右的1//eor:		1010111100//~eor:		0101000011//~eor+1:	0101000100//&:		0000000100int rightOne = eor & (~eor+1);for(int cur:arr){//将最右1位置为1的数相异或if((cur & rightOne) == 1){onlyOne ^= cur;}}System.out.println(onlyOne+" "+(eor ^ onlyOne));
}

🍔对数器

准备两个算法A和B，A为追求时间复杂度的算法（一般为待测试方法），B为不追求时间复杂度容易实现的算法，使用定量的随机数据分别代入A和B中进行运算，将结果进行比较，当测试数据集扩大到一定量时结果依旧准确，说明算法A正确。

不依赖线上OJ平台且测试数据更准确

// 以排序算法为例，准备一个随机数生成器，生成指定数量的数据，分别使用待测算法和稳定算法进行排序，排序完成后比较排序结果，若在一定的数据量下，所有数据集均测试成功，则代表待测算法通过
public static void main(String[] args){// 测试数量int testTime = 5000000;int maxSize = 100;int maxValue = 100;boolean succeed = true;for(int i = 0; i < testTime; i++){// 通过随机数生成器生成指定数量的数据集int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);// 分别使用两种算法进行排序bubbleSort(arr1);comparator(arr2);// 比较排序结果if(!isEqual(arr1, arr2)){succeed = false;break;}}System.out.println(succeed ? "Pass!" : "Fail!");}public static void comparator(int[] arr){// 使用系统提供的排序做对数器Arrays.sort(arr);}// 依次比较排序结果public static boolean isEqual(int[] arr1, int[] arr2){for (int i = 0; i < arr1.length; i++){if(arr1[i] != arr2[i]){return false;}}return true;}// 随机数生成器public static int[] generateRandomArray(int maxSize, int maxValue){// (int)(Math.random() * N)  ->  [0,N-1]所有整数，等概率随机返回一个// 生成随机长度的数组int[] arr = new int[(int)(Math.random() * (maxSize + 1))];// 为数组赋值随机数for(int i = 0; i < arr.length; i++){arr[i] = (int)(Math.random() * (maxValue + 1)) - (int)(Math.random() * maxValue);}return arr;}public static int[] copyArray(int[] arr){if(arr == null){return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++){res[i] = arr[i];}return res;}

🎄时间、空间复杂度

🍟空间复杂度基本概念

空间复杂度为算法流程实现过程中，额外开辟的辅助空间大小，其判定、表示方式和时间复杂度相同。

public static void swap(int a, int b){int t = a;a = b;b = t;
}
// 额外开辟了一个t的辅助空间，因此为O(1)public static void swapArray(int[] arr1, int[] arr2){// arr1.length == arr2.lengthint[] arr3 = new int[arr1.length];for(int i = 0, i < arr1.length; i++){arr3[i] = arr2[i];arr2[i] = arr1[i];arr1[i] = arr3[i];}
}
// 额外开辟了一个n大小的辅助空间，因此空间复杂度为O(n)

🌭时间复杂度基本概念

常数操作：一个操作和样本的数据量没有关系，每次都是固定时间完成操作，叫做常数操作。
时间复杂度为一个算法流程中，常数操作数量T(n)的一个指标，这个指标反映了当前算法在数据量增加时执行效率减缓的速度，常用O（读作big O）表示。具体来说，需要算出算法流程中发生了多少常数操作，进而总结成常数操作数量的表达式。

在表达式中，只要去除系数的最高项(n相对于n²，在数据量激增的背景下，可忽略不计)，例如:

T(n) = 2n³+7n²-9 -> O(n³)
```
for(int i = 0; i < n; i++){sum += i;
}
sum *=2
// T(n)= n + 1  ->  O(n)for(int i = 0; i < n; i++){for(int j = 0; j <= i; j++){sum += j;}
}
sum ^= 3
// T(n)= n(n-1)/2 + 1  ->  O(n^2)
```
评价算法流程的好坏，优先观察时间复杂度的指标，进而分析不同数据样本下的实际运行时间，也就是“常数项”时间。
对于更复杂的递归时间复杂度运算，可提前浏览递归中的Master公式内容。
常见的算法时间复杂度由小到大依次为: Ο(1)＜Ο(logn)＜Ο(n)＜Ο(nlogn)＜Ο(n^k) ＜ Ο(2ⁿ)，随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低

🍿基本的排序算法的时间复杂度

✨冒泡排序/起泡排序(Bubble Sort)

实现思路
- 从第一位起，分别依次比较下标为（1，2）、（2，3）、（3，4）…的值，若前者大于后者，则交换两个数
- 从头到尾执行完一轮后，数组中最大数被移动到数组尾部，继续进行第二轮、第三轮比较，分别将第二大、第三大的数移动到尾部
- 总共进行n-1轮，每轮选择最大值的过程就像是水中气泡冒出的过程，逐渐浮出到水面
图示：

代码实现

public static void bubbleSort(int[] arr){if(arr == null || arr.length < 2){return;}for(int i = arr.length - 1; i > 0; i--){for(int j = 0; j < i; j++){if(arr[j] > arr[j+1]){swap(arr, j, j+1);}}}
}// 交换两数的值
public static void swap(int[] arr, int i, int j){arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];
}

时间复杂度

O(n²)

✨插入排序（Insertion Sort）

实现思路
- 每次排序前0~n位置的数，第一次使0-0位置有序，第二次为0-1，依次为0-2，0-3，0-n…
- 每次从n位置往前看，当n位置比前方数（假设为k位置的数）小，交换两位数，再比较n位置和k-1位置，重复操作，当k==0 or n位置数大于k位置数时结束，增大范围（n+1）继续比较
  
  取其中一次排序做解析：
  
  假设0-4范围已经排序，当前排序0-5范围
  
  arr = [2，5，8，9，10，4，23，3]
  
  （1）比较4和10，4<10，交换位置
  
  arr = [2，5，8，9，4，10，23，3]
  
  （2）比较4和9，4<9，交换位置
  
  arr = [2，5，8，4，9，10，23，3]
  
  （3）比较4和8，4<8，交换位置
  
  arr = [2，5，4，8，9，10，23，3]
  
  （4）比较4和5，4<5，交换位置
  
  arr = [2，4，5，8，9，10，23，3]
  
  （5）比较4和2，4>2，0-5范围排序完成，继续排序0-6范围…
图示：

代码实现

public static void insertionSort(int[] arr){if(arr == null || arr.length < 2){return;}// 分别实现0~i的有序排列for(int i = 1; i < arr.length; i++){for(int j = i - 1; j >=0 && arr[j] > arr[j + 1]; j--){swap(arr, j, j+1);}}}// 交换两个数的值public static void swap(int[] arr, int i, int j){arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}

时间复杂度：对于插入排序，数据状况不同，时间复杂度不同

7654321 => O(n²)

1234567 => O(n)

时间复杂度修正，按照最差情况估计，因此时间复杂度为O(n²)

🧂递归行为的时间复杂度

递归实质是使用系统栈实现的过程
Master公式——>计算递归时间复杂度

T(N) = a * T(N/b) + O(N^d)

T(N):父问题的规模

a:子问题执行的次数

T(N/b):子问题的规模

O(N^d):剩余部分的时间复杂度

log_ba < d —— O(N^d)

log_ba > d —— O(N^log_ba)

log_ba == d —— O(N^d*logN)

应用

用递归方法查找数组最大值

时间复杂度：T(n) = 2 * T(n / 2) + O(1) --> a = 2, b = 2, d = 0 --> O(n<sup>log<sub>b</sub>a</sup>) = O(n)

public static int getMax(int[] arr){return process(arr, 0, arr.length - 1);
}
// arr[L...R]范围上求最大值
public static int process(int[] arr, int L, int R){if(L == R){  // arr[L...R]范围上只有一个数，直接返回 return arr[L];}int mid = L + ((R - L) >> 1);  // 中点int leftMax = process(arr, L, mid);int rightMax = process(arr, mid+1, R);return Math.max(leftMax, rightMax);
}

✨二分法

二分法更像是一种思想，将数据量一分为二，只关注需要的部分，避免多余的操作，由于其时间复杂度非常低，因此在实际应用中使用频率比较高
优化

对于中值mid = (L+R)/2，L+R可能会溢出，因此优化为mid = L+(R-L)/2

int mid = L + ((R - L) >> 1)	// >>比/的运行速度快

图示

请添加图片描述

应用

在一个有序数组中，找某个数是否存在，若存在返回其下标位置，否则返回-1

  public static int binarySearch(int[] arr, int aim, int L, int R){// 被查找数不存在，返回-1if(aim < arr[L] || aim > arr[R]){return -1;}// 中点值int mid = L + ((R - L) >> 1);// 中点为目标查找数，返回下标if(aim == arr[mid]){return mid;}else if(aim > arr[mid]){// 目标数在右侧，对右侧使用二分法return binarySearch(arr, aim, mid + 1, R);}else{// 目标数在左侧，对左侧使用二分法return binarySearch(arr, aim, L, mid - 1);}}
// 时间复杂度：T(n) = 1 * T(n / 2) + O(1)  -->  = O(logn)

在一个有序数组中，找>=某个数最左侧的位置

// 该问题与上一题目相似，不同点在于上一题目查找到即退出，该问题中，应该坚持查找到最后一个数
public static int binarySearch(int[] arr, int aim, int L, int R){int mid = L + ((R - L) >> 1);// 查找到最后一个数，返回下标if(L == R){return mid;}// aim在中点的左侧或aim为中点，继续向左侧查找（aim在数组中可能出现多次，因此即使查找到aim也应继续查找，以保证找到最左侧位置）if(arr[mid] >= aim){return binarySearch(arr, aim, L, mid - 1);}else{return binarySearch(arr, aim, mid + 1, R);}}
// 时间复杂度：T(n) = 1 * T(n / 2) + O(1)  -->  = O(logn)

局部最小值：在一个无序数组中，相邻两数不相等，有两种情况记为局部最小：

（1）第一个数小于第二个数或最后一个数小于倒数第二个数

（2）对于中间的任何一个数，需要满足a[i-1] > a[i] and a[i] < a[i+1]

要求找出一个局部最小值

// （消除刻板印象）二分法并非排序才能使用
// 1.对于第一种情况的局部最小值直接判断
// 2.对于第二种情况：取中值判断是否为局部最小值，若不是，选择数值小于M的一侧（因为相邻两数不相等，故一定至少存在一个局部最小值）继续二分
public static void main(String[] args) {int arr[] = {7, 3, 1, 4, 5, 6, 7, 8, 9};int R = arr.length - 1;// 判断边界局部最小值if (arr[0] < arr[1]) {System.out.println(0);} else if (arr[R] < arr[R - 1]) {System.out.println(R);} else {System.out.println(localMinimum(arr, 0, R));}
}public static int localMinimum(int[] arr, int L, int R) {// 非边界局部最小值的判断int mid = L + ((R - L) >> 1);// mid为局部最小值if (arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1]) {return mid;} else if (arr[mid] > arr[mid - 1]) {return localMinimum(arr, L, mid - 1);} else {return localMinimum(arr, mid + 1, R);}
}
// 时间复杂度：T(n) = 1 * T(n / 2) + O(1)  -->  = O(logn)

✨归并排序

排序过程
- 将待排序数组A分为两部分，中点记为M，左侧、右侧分别记为数组L、R，将L、R进行排序（递归实现）
- 归并过程：构建辅助数组A＇（大小为A的大小），将指针分别指向L和R的最左侧元素，比较两元素的大小，将较小者添加到A＇中同时指针后移
- 重复操作直至L或R越界（代表前半元素排序完毕），将A中剩余元素添加到A＇中即可
- 将A＇赋值给A
图示

代码实现

// 处理数组，保证数组递归到两个单独的数字public static void progress(int[] arr, int L, int R){// 保证progress一直分割到一个一个数时，左右progress进行mergeif(L == R){return;}int M = L + ((R - L) >> 1);progress(arr, L, M);progress(arr, M + 1, R);merge(arr, L, M, R);}public static void merge(int[] arr, int L, int M, int R){// 构建辅助数组,注意数组大小不为arr.lengthint[] help = new int[R - L + 1];int i = 0;int p1 = L;int p2 = M + 1;while(p1 <= M && p2 <= R){help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}while(p1 <= M){help[i++] = arr[p1++];}while(p2 <= R){help[i++] = arr[p2++];}for(i = 0; i < help.length; i++){arr[L + i] = help[i];}}
// 时间复杂度：T(n) = 2 * T(n / 2) + O(n)  -->  = O(nlogn)

应用

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

例子：[1,3, 4,2, 5] -> 1左边比1小的数，没有; 3左边比3小的数，1; 4左边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、2；所以小和为1+1+3+1+1+3+4+2=16

// 将左侧比自身小的数相加可以转换为：将各数自身的k倍相加（k为右侧比自己大的数的数量）
public static int smallSum(int[] arr){if(arr.length < 2 || arr == null){return 0;}return progress(arr, 0, arr.length - 1);}public static int progress(int[] arr, int L, int R){if(L == R){return 0;}int M = L + ((R - L) >> 1);// 注意三组值分别相加，progress分别表示左右侧数组小和数，merge表示两侧数组合并后产生的新的小和数量return progress(arr, L, M) + progress(arr, M + 1, R) + merge(arr, L, M, R);}public static int merge(int[] arr, int L, int M, int R){int[] help = new int[R - L + 1];int i = 0;int p1 = L;int p2 = M + 1;int res = 0;while(p1 <= M && p2 <= R){// 将右侧比自己大的数的数量*自身大小 即为 该数在当前数组中产生的小和，例如：// 左侧：2 4 5，右侧：6 9 14。4当前范围中产生的小和为3*4=12（当左右合并后，4不会与右侧再次进行比较，故不必担心小和会重复产生）// 此方法避开了遍历循环，巧妙地将时间复杂度O(n) -> O(1)res += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= M){help[i++] = arr[p1++];}while (p2 <= R){help[i++] = arr[p2++];}for (i = 0; i < help.length; i++){arr[L + i] = help[i];}return res;};
// 时间复杂度：T(n) = 2 * T(n / 2) + O(n)  -->  = O(nlogn)

✨荷兰国旗问题

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)

// 将左侧划分出小于等于的区域（LE区），依次从最开始遍历元素，当元素小于等于num值，将元素与LE区下一个元素互换，同时LE区边界+1（意为将元素划入LE区），当元素大于num值，跳过，进行下一元素的判断
public static void netherLandsFlag(int[] arr, int aim){// p代表小于等于num区域的边界下标int p = -1;// arr[i]<=num，将arr[i]和小于等于区域的下一个数交换，同时区域范围扩大1for (int i = 0; i < arr.length; i++){if(arr[i] <= aim){int temp = arr[i];arr[i] = arr[++p];arr[p] = temp;}}}