算法-经典排序算法

# 经典算法思想

## 分治法（Divide and Conquer）

分治法(Divide and Conquer，也称为“分而治之法”)是一种很重要的算法，我们可以应用分治法来逐一拆解复杂的问题，核心思想就是将一个难以直接解决的大问题依照相同的概念分割成两个或更多的子问题，以便名个击破。

![image.png](/static/img/4fb979feaafa2aace274a299c4616224.image.webp)

其实任何一个可以用程序求解的问题所需的计算时间都与其规模与复杂度有关，问题的规模越小，越容易直接求解，因此可以不断分解问题，使子问题规模不断缩小,让这些子问题简单到可以直接解决，再将各子问题的解合并，最后得到原问题的解答。


### 特点与应用

- 子问题相互独立
- 递归实现
- 归并排序：将数组拆分为两半，递归排序后合并有序子数组。
- 快速排序：通过基准值分割数组，递归处理左右分区


### 代码实现（归并排序）

```java
public class MergeSort {
 public static void mergeSort(int[] arr, int left, int right) {
 if (left < right) {
 int mid = left + (right - left) / 2;
 mergeSort(arr, left, mid); // 分解左半部分
 mergeSort(arr, mid + 1, right); // 分解右半部分
 merge(arr, left, mid, right); // 合并有序子数组
 }
 }

 private static void merge(int[] arr, int left, int mid, int right) {
 int[] temp = new int[right - left + 1];
 int i = left, j = mid + 1, k = 0;

 while (i <= mid && j <= right) {
 temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
 }
 while (i <= mid) temp[k++] = arr[i++];
 while (j <= right) temp[k++] = arr[j++];

 System.arraycopy(temp, 0, arr, left, temp.length);
 }

 public static void main(String[] args) {
 int[] arr = {5, 3, 8, 4, 2};
 mergeSort(arr, 0, arr.length - 1);
 System.out.println(Arrays.toString(arr)); // 输出[2, 3, 4, 5, 8]
 }
}
```

**代码解读：**

分解：递归将数组分为左右两半

合并：将两个有序子数组合并为一个有序数组


## 递归法（Recursion）

递归是一种很特殊的算法，分治法和递归法很像一对孪生兄弟，都是将一个复杂的算法问题进行分解，让规模越来越小，最终使子问题容易求解。只不过递归法通过函数调用自身解决问题，需定义基线条件和递归条件。


![image.png](https://blog.liushigong.cn/static/img/4a68bcefd142ee2600c0599c942798f5.image.webp)


### 特点与应用

- 代码简洁
- 经典应用：树遍历、汉诺塔

### 汉诺塔问题

> 给定三根柱子，记为 A,B,C，其中 A 柱子上有 n 个盘子，从上到下编号为 0 到 n−1 ，且上面的盘子一定比下面的盘子小。问：将 A 柱上的盘子经由 B 柱移动到 C 柱最少需要多少次？打印出每个步骤
> 
> 移动时应注意：
> - 一次只能移动一个盘子
> - 大的盘子不能压在小盘子上


**思路**

先从简单的三个盘子试试，可以先不看答案自己画一画，挺好玩的，注意规则噢

![image.png](/static/img/6ec28eba4b4fb3b7ad9b0b6af3a29077.image.webp)

n个盘子从A柱到C柱最少移动次数

![image.png](/static/img/ba88aa37d5b721c8ae115a3b5b303891.image.webp)

**代码实现**

```java
public class HanoiTower {
 public static void move(int n, char from, char to, char aux) {
 if (n == 1) {
 System.out.println("移动盘子1从" + from + "到" + to);
 return;
 }
 move(n - 1, from, aux, to);
 System.out.println("移动盘子" + n + "从" + from + "到" + to);
 move(n - 1, aux, to, from);
 }

 public static void main(String[] args) {
 move(3, 'A', 'C', 'B'); // 3层汉诺塔解法
 }
}
```

**代码解读**

将n个盘子分解为移动n-1个盘子的子问题

时间复杂度：O(2ⁿ)


## 动态规划（Dynamic Programming, DP）

通过记录子问题的解避免重复计算，适用于有重叠子问题和最优子结构的问题。

动态规划法(Dynamic Programming Algorithm，DPA)类似于分治法，核心思想是如果一个问题的答案与子问题相关，就将大问题拆解成各个小问题，与分治法最大的不同是可以让每一个子问题的答案被存储起来，以供下次求解时直接取用。这样的做法不但可以减少再次计算的时间，而且可以将这些解组合成大问题的解，故而使用动态规划可以解决重复计算的问题。

动态规划法是分治法的延伸。当用递归法分割出来的问题“一而再，再而三”出现时，就可以运用记忆(Memorization)法来存储这些问题。与分治法不同的地方在于，动态规划法增加了记忆机制的使用，将处理过的子问题的答案记录下来，避免重复计算。


### 特点与应用

- 自底向上或自顶向下（记忆化搜索）
- 时间复杂度优化显著
- 最短路径问题（Floyd-Warshall算法）
- 斐波那契数列
- 背包问题
- 最长公共子序列
- 最长公共子串
- 矩阵最大值（和以及积）


### 斐波那契数列

斐波那契数列是指这样一个数列：0，1，1，2，3，5，8，13，21，34，55，89……这个数列从第3项开始 ，每一项都等于前两项之和。


![image.png](/static/img/ecba5aa12fb2385f5676c8f4e29c3f5c.image.webp)

对于斐波那契数列采用的是动态规划法，那么已计算过的数据就不必重复计算了，也不会再往下递归，这样可以提高性能。

![image.png](https://blog.liushigong.cn/static/img/e22182c57ec9087706bce5e8db376cc2.image.webp)

**代码实现**

```java
public class Fibonacci {
 // 动态规划实现
 public static int fibDP(int n) {
 if (n <= 1) return n;
 int[] dp = new int[n + 1];
 dp[0] = 0;
 dp[1] = 1;
 for (int i = 2; i <= n; i++) {
 dp[i] = dp[i - 1] + dp[i - 2];
 }
 return dp[n];
 }

 public static void main(String[] args) {
 System.out.println(fibDP(10)); // 输出55
 }
}
```

**代码解读：**

使用数组 dp 存储中间结果

递推公式：dp[i] = dp[i-1] + dp[i-2]


## 枚举法（Brute Force）

枚举法(又称为穷举法)，是我们在日常工作中使用最多的一种算法，核心思想是列举所有的可能。根据问题的要求，逐一列举问题的解答，或者为了便于解决问题把问题分为不重复、不遗漏的有限种情况，逐一列举各种情况，并加以解决，最终达到解决整个问题的目的。像枚举法这种分析问题、解决问题的方法，得到的结果总是正确的，缺点是速度太慢。


### 特点与应用

- 实现简单
- 时间复杂度：O(n)
- 适合小规模的问题
- 密码破解：尝试所有可能的字符组合


### 代码实现

使用穷举法来实现以下题目

> 今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？

```java
public class Permutations {
 public static void enumeratingAlgorithm() {
 int head = 35, foot = 94;
 int j;
 for (int i = 0; i <= 35; i++) {
 // i代表鸡的数量 
 j = head - i;
 // j代表兔子的数量
 if (i * 2 + j * 4 == foot) {
 System.out.printf("鸡的个数为[ %d ]只,兔子的个数为[ %d ]只。", i, j);
 return;
 }
 }
 System.out.println("此题无解！你家鸡和兔子有三只脚的吧？");
 }
}
```

**代码解读：**

通过题目可以知道，鸡和兔的总数量为0-35只(每个动物都是一个脑袋，这就不用说了吧)，我们可以假设鸡为0，兔子为35，用鸡的个数*2+兔子的个数*4就可以得到总的脚的数量，如果等于94，那么便是答案，如果不等，则鸡的数量+1，兔子数量-1，依次类推，穷举所有情况直到得到答案


## 回溯法（Backtracking）

回溯法(Backtracking)也是枚举法的一种，对于某些问题而言，回溯法是一种可以找出所有(或一部分)解的一般性算法，同时避免枚举不正确的数值。一旦发现不正确的数值，就不再递归到下一层，而是回溯到上一层，以节省时间，是一种走不通就退回再走的方式。它的特点主要是在搜索过程中寻找问题的解，当发现不满足求解条件时就回湖(返回)，尝试别的路径，避免无效搜

![image.png](/static/img/b5b06d0bb66eb9de8e87da9303a75d7e.image.webp)

### 特点

- 递归实现
- 时间复杂度高（指数级）
- 数独求解
- 组合数生成
- A*寻路算法（了解）
- 地图着色算法
- N 皇后问题
- 最优加工顺序
- 旅行商问题

回溯法可以应用于以下类型的问题：

- 排列和组合问题：例如求解全排列、子集合等问题，回溯法可以系统地生成所有可能的组合并逐一验证。
- 决策问题：如八皇后问题、数独填充、图的着色问题等，这些问题需要在多个选择中找到符合特定约束的解。
- 优化问题：如旅行商问题（TSP）和其他需要找到最优解的问题，回溯法可以遍历所有可能的解，找到成本最低或收益最高的解。
- 分割问题：例如分割等和子集、装箱问题等，需要将集合分割成满足特定条件的多个子集。


### N皇后问题

八皇后问题，是一个古老而著名的问题.该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法?


![image.png](https://blog.liushigong.cn/static/img/1ecce3e32c9cedaf6a4faa5d212e53c4.image.webp)

将8皇后问题推演一下，就可以得到我们的N皇后问题了。

N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，使其不能互相攻击。(同一行、同一列、同一斜线上的皇后都会自动攻击)那么问，有多少种摆法？


**代码解读：**

```java
public class NQueens {
 private static List<List<String>> result = new ArrayList<>();

 public static List<List<String>> solveNQueens(int n) {
 char[][] board = new char[n][n];
 for (char[] row : board) Arrays.fill(row, '.');
 backtrack(board, 0);
 return result;
 }

 private static void backtrack(char[][] board, int row) {
 if (row == board.length) {
 result.add(convertBoard(board));
 return;
 }
 for (int col = 0; col < board.length; col++) {
 if (isValid(board, row, col)) {
 board[row][col] = 'Q';
 backtrack(board, row + 1);
 board[row][col] = '.'; // 回溯
 }
 }
 }

 private static boolean isValid(char[][] board, int row, int col) {
 // 检查列、左上对角线、右上对角线
 for (int i = 0; i < row; i++) {
 if (board[i][col] == 'Q') return false;
 int left = col - (row - i), right = col + (row - i);
 if (left >= 0 && board[i][left] == 'Q') return false;
 if (right < board.length && board[i][right] == 'Q') return false;
 }
 return true;
 }

 private static List<String> convertBoard(char[][] board) {
 List<String> res = new ArrayList<>();
 for (char[] row : board) res.add(new String(row));
 return res;
 }

 public static void main(String[] args) {
 System.out.println(solveNQueens(4).size()); // 输出2（4皇后有2种解法）
 }
}
```

**代码解读：**

逐行放置皇后，检查冲突

回溯时重置棋盘状态（board[row][col] = '.'）



## 贪心法（Greedy Algorithm）

贪心算法（greedy algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

### 思路

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，其选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时， 就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

> 贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。
> 
> 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

**题解思路可分为3个步骤**

1. 将问题分解为多个子问题。
2. 选择合适的贪心策略，得到每一个子问题的局部最优解。
3. 将子问题的局部最优解合并成原问题的最优解。


:::tip{title="贪心算法存在的问题"}
贪心算法是把求解的问题分成若干个子问题求最优解，不能保证 **最终解是最佳的**。

因为贪心算法总是从局部出发，并没从整体考虑，贪心算法容易过早做出决定，所以只能求出满足某些约東条件的解，而有时在某些问题上还是可以得到最优解的。
:::


### 解题策略

要确定一个问题是否适合用贪心算法求解，必须证明每一步所作的贪心选择最终导致问题的整体最优解，使用贪心策略解题需要考虑以下两个问题：

- 该问题是否适合使用贪心策略求解，也就是该问题是否具有贪心选择性质
- 制定贪心策略，以达到问题的最优解或较优解

:::info{title="证明的大致过程"}
首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。
:::

### 经典应用

贪心策略的经典算法

#### 分数背包问题

给定 n 个物品，每个物品都有重量 w[i] 和价值 v[i]，同时有一个容量为 C 的背包。与 0-1 背包问题不同的是，在分数背包问题中，物品可以分割成任意比例放入背包，目标是在背包容量限制内选择物品放入背包，使得背包中物品的总价值最大。

![image.png](/static/img/8c15c03393444bb99308bcead4f4228d.image.webp)


**贪心策略确定**

最大化背包内物品总价值，本质上是最大化单位重量下的物品价值。由此便可推理出贪心策略。

1. 将物品按照单位价值从高到低进行排序。
2. 遍历所有物品，每轮贪心地选择单位价值最高的物品。
3. 若剩余背包容量不足，则使用当前物品的一部分填满背包。


![image.png](/static/img/e0230fbd5ca18a3c29b3f060ba1f2d36.image.webp)


**代码实现**

建立了一个物品类 Item ，以便将物品按照单位价值进行排序。循环进行贪心选择，当背包已满时跳出并返回解：

```java
/* 物品 */
class Item {
 int w; // 物品重量
 int v; // 物品价值

 public Item(int w, int v) {
 this.w = w;
 this.v = v;
 }
}

/* 分数背包：贪心 */
double fractionalKnapsack(int[] wgt, int[] val, int cap) {
 // 创建物品列表，包含两个属性：重量、价值
 Item[] items = new Item[wgt.length];
 for (int i = 0; i < wgt.length; i++) {
 items[i] = new Item(wgt[i], val[i]);
 }
 // 按照单位价值 item.v / item.w 从高到低进行排序
 Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.v / item.w)));
 // 循环贪心选择
 double res = 0;
 for (Item item : items) {
 if (item.w <= cap) {
 // 若剩余容量充足，则将当前物品整个装进背包
 res += item.v;
 cap -= item.w;
 } else {
 // 若剩余容量不足，则将当前物品的一部分装进背包
 res += (double) item.v / item.w * cap;
 // 已无剩余容量，因此跳出循环
 break;
 }
 }
 return res;
}
```

内置排序算法的时间复杂度通常为O(logn) ，空间复杂度通常为 O(logn) 或 O(n)，取决于编程语言的具体实现。除排序之外，在最差情况下，需要遍历整个物品列表，因此时间复杂度为O(n)，其中n为物品数量。由于初始化了一个 Item 对象列表，因此空间复杂度为 O(n)。


**正确性证明**

采用反证法。假设物品 x 是单位价值最高的物品，使用某算法求得最大价值为 res ，但该解中不包含物品 x。

现在从背包中拿出单位重量的任意物品，并替换为单位重量的物品x。由于物品x的单位价值最高，因此替换后的总价值一定大于 res 。这与 res 是最优解矛盾，说明最优解中必须包含物品x。

对于该解中的其他物品，我们也可以构建出上述矛盾。总而言之，单位价值更大的物品总是更优选择，这说明贪心策略是有效的。

将物品重量和物品单位价值分别看作一张二维图表的横轴和纵轴，则分数背包问题可转化为“求在有限横轴区间下围成的最大面积”。这个类比可以帮助我们从几何角度理解贪心策略的有效性。

![image.png](/static/img/e5edc129ada714199246facf20cc74e3.image.webp)


#### 找零问题

给定一个总金额和一系列不同面额的零钱，如何以最少的零钱数量来支付这个金额。‌在找零问题中，贪心算法的核心思想是每一步尽可能使用面值最大的零钱，从而减少使用的零钱数量。

**贪心策略确定**

将原问题分解为一系列子问题，每个子问题对应一个具体的找零操作。

- 贪心选择‌：对每个子问题求解时，选择当前看起来“最优”的解法，即尽可能使用面值最大的零钱。
- 合并解‌：累计局部最优解形成全局解，最终得到最少的零钱数量。

**代码实现**

```java
public class CoinChange {
 public static int minCoins(int[] coins, int amount) {
 Arrays.sort(coins); // 需降序排序
 int count = 0, index = coins.length - 1;
 while (amount > 0 && index >= 0) {
 if (coins[index] <= amount) {
 int num = amount / coins[index];
 count += num;
 amount -= num * coins[index];
 }
 index--;
 }
 return (amount == 0) ? count : -1;
 }

 public static void main(String[] args) {
 int[] coins = {1, 5, 10, 25}; // 美分硬币
 System.out.println(minCoins(coins, 63)); // 输出6（25+25+10+1+1+1）
 }
}
```

**正确性证明‌**

通过数学归纳或替换论证验证算法的正确性，尽管贪心策略不一定总是正确的，但在许多情况下能够提供足够好的解决方案。


## 总结

掌握这些算法思想可覆盖90%的编程问题，实际应用中需根据问题特点灵活组合使用。

| 算法思想 |	适用场景	| 时间复杂度 |
| --- | --- | --- |
| 分治法	| 大规模问题分解	| O(n log n)| 
| 递归法	| 树形结构问题	| 取决于问题规模| 
| 动态规划	| 重叠子问题优化	| O(n²) ~ O(n³)| 
| 枚举法	| 小规模暴力求解	| O(2ⁿ) ~ O(n!)| 
| 回溯法	| 组合优化问题	| O(n!)| 
| 贪心法	| 局部最优解场景	| O(n) ~ O(n log n)|

算法-核心算法思想

大家可能会想，怎么评估一个算法的好坏呢？ 本章节就是在学习算法前，先需要掌握一些理论基础。



# 评估算法优劣的核心指标是什么？

## 时间复杂度 O(f(n))

把某个算法执行步骤的计数来作为衡量运行时间的标准

### 衡量标准

在一个完全理想状态下的计算机中，我们定义 T(n)来表示程序执行所要花费的时间，其中n代表数据输入量。当然程序的最坏运行时间(Worse Case Executing Time)或最大运行时间是时间复杂度衡量的标准。

时间复杂度的衡量标准，一般以 Big-Oh 表示。常见的 Big-Oh

| Big-Oh | 名称 | 描述 |
| --- | --- | --- |
| O(1) | 常数时间(Constant Time) | 表示算法的运行时间是一个常数倍 |
| O(n) | 称为线性时间(Linear Time) | 表示执行的时间会随着数据集合的大小而线性增长|
| O(log2n) | 次线性时间(Sub-Linear Time) | 成长速度比线性时间慢，而比常数时间快 |
| O(n^2) | 平方时间(Quadratic Time) | 称为，算法的运行时间会成二次方的增长 |
| O(n^3) | 立方时间(Cubic Time) | 算法的运行时间会成三次方的增长 |
| O(2^n) | 指数时间(Exponential Time) | 算法的运行时间会成2 的 n 次方增长。例如，解决Nonpolynomial Problem 问题算法的时间复杂度为 O(2") |
| O(nlog2n) | 线性乘对数时间 | 称为，介于线性和二次方增长的中间模式 |


由于在估算算法复杂度时采取“宁可高估不要低估”的原则，因此估计出来的复杂度是算法真正所需运行时间的上限。请大家看以下范例，以了解时间复杂度的意义。

> 范例：假如运行时间 T(n)=3㎡'+2㎡+5n，求时间复杂度。
> 
> 解答：首先找出常数c与 n。当 n=0、c=10 时，若 n>no，则 3n'+2㎡'+5n<10㎡，因此得知时间复杂度为 O(m^3)。


### 时间复杂度的意义

上面的范例中抹掉了好多东西，只剩下了一个最高阶项啊… 那这个东西有什么意义呢？

**时间复杂度的意义在于**

> 当我们要处理的样本量很大很大时，我们会发现低阶项是什么不是最重要的；每一项的系数是什么，不是最重要的。真正重要的就是最高阶项是什么。

这就是时间复杂度的意义，它是衡量算法流程的复杂程度的一种指标，该指标只与数据量有关，与过程之外的优化无关。


### 成长率

在分析算法的时间复杂度时，往往用函数来表示它的成长率(Rate ofGrowth)，其实时间复杂度是一种“渐近表示法”(Asymptotic Notation)

![image.png](https://blog.liushigong.cn/static/img/0081534ba202a6dd65f5d6073456edcb.image.webp)

不同的时间复杂度之间在不同数量下的处理速率

![image.png](https://blog.liushigong.cn/static/img/4626fcc48f3309ee82b9595e5c405704.image.webp)



## 空间复杂度

你要实现一个算法流程，在实现算法流程的过程中，你需要开辟一些空间来支持你的算法流程。

- 作为输入参数的空间，不算额外空间。
- 作为输出结果的空间，也不算额外空间。

因为这些都是必要的、和现实目标有关的。所以都不算。

但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间，如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。

### 常见的空间复杂度有下面几种情形。

**常量空间**

当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作O(1)。例如 `int i=3`

**线性空间**

当算法分配的空间是一个线性的集合(如列表)，并且集合大小和输入规模n成正比时，空间复杂度记作O(n)。例如 `int[] array = {1,2,3}`

**二维空间**

当算法分配的空间是一个二维列表集合，并且集合的长度和宽度都与输入规模n成正比时，空间复杂度记作O(n2)。例如 `int[][] array = new int[10][10]`

**递归空间**

递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合，但是计算机在执行程序时，会专门分配一块内存，用来存储“函数调用栈”。

![image.png](https://blog.liushigong.cn/static/img/0d664bae820344ce99127069d21608ae.image.webp)

由上面“函数调用栈”的出入栈过程可以看出，执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n)。


### 时间与空间的取舍

人们之所以花大力气去评估算法的时间复杂度和空间复杂度，其根本原因是计算机的运算速度和空间资源是有限的。虽然目前计算机的CPU处理速度不断飙升，内存和硬盘空间也越来越大，但是面对庞大而复杂的数据和业务，我们仍然要精打细算，选择最有效的使用方式。

但是，正所谓鱼和能掌不可兼得。很多时候，我们不得不在时间复杂度和空间复杂度之间进行取舍。

```java
public class DuplicateExample {
 // 方案 1：暴力法（时间换空间）
 // 时间复杂度 O(n²)，空间复杂度 O(1)
 public static boolean hasDuplicateBruteForce(int[] nums) {
 for (int i = 0; i < nums.length; i++) {
 for (int j = i + 1; j < nums.length; j++) {
 if (nums[i] == nums[j]) {
 return true;
 }
 }
 }
 return false;
 }

 // 方案 2：哈希表（空间换时间）
 // 时间复杂度 O(n)，空间复杂度 O(n)
 public static boolean hasDuplicateHashSet(int[] nums) {
 Set<Integer> seen = new HashSet<>();
 for (int num : nums) {
 if (seen.contains(num)) {
 return true;
 }
 seen.add(num);
 }
 return false;
 }

 public static void main(String[] args) {
 int[] nums = {1, 2, 3, 1};
 
 // 暴力法：通过双重循环比较所有元素对，省去额外空间，但时间效率低。
 System.out.println("暴力法结果: " + hasDuplicateBruteForce(nums)); // true
 
 // 哈希表：用 HashSet 存储已遍历元素，以空间换时间，效率更高。
 System.out.println("哈希表结果: " + hasDuplicateHashSet(nums)); // true
 }
}


```

在绝大多数时候，时间复杂度更为重要一些，我们宁可多分配一些内存空间，也要提升程序的执行速度。

### 取舍策略总结

1. 时间换空间：当内存资源紧张时（如嵌入式系统），选择低空间复杂度的算法。
2. 空间换时间：当时间要求严格时（如高频交易系统），选择低时间复杂度的算法。
3. 平衡选择：根据实际场景的数据规模（如 n 的大小）和硬件条件灵活调整。

:::info{title="相关信息"}
此外，说起空间复杂度就离不开**数据结构**，可以通过[「算法-数据结构基础」](/post/33)章节去掌握这部分内容。**时间复杂度 和 空间复杂度 都是学好算法的重要前提，一定要牢牢掌握哦!**
:::


## 常数项时间（实现细节决定）

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

### 常见的常数时间的操作

- 算术运算（+、-、*、/、% 等）
- 位运算（>>、>>>、<<、|、&、^等）
- 赋值、比较、自增、自减操作等
- 数组寻址操作

总之，执行时间固定的操作都是常数时间的操作。反之，执行时间不固定的操作，都不是常数时间的操作。


### 算法流程的常数项

我们会发现，时间复杂度这个指标，是忽略低阶项和所有常数系数的，难道同样时间复杂度的流程，在实际运行时候就一样的好吗？

结果当然不是，时间复杂度只是一个很重要的指标而已，如果两个时间复杂度一样的算法，你还要去在时间上拼优劣，就进入到拼常数时间的阶段，简称拼常数项。


### 算法流程的常数项的比拼方式

放弃理论分析，生成随机数据直接测。

**为什么不去理论分析？**

不是不能纯分析，而是没必要。因为不同常数时间的操作，虽然都是固定时间，但还是有快慢之分的。
比如，位运算的常数时间原小于算术运算的常数时间，这两个运算的常数时间又远小于数组寻址的时间。所以如果纯理论分析，往往会需要非常多的分析过程。都已经到了具体细节的程度，莫不如交给实验数据好了。


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

1. 想象该算法流程所处理的数据状况，要按照最差情况来。
2. 把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数时间的操作。
3. 如果数据量为N，看看基本动作的数量和N是什么关系。


### 位运算

位运算直接操作整数的二进制位，是计算机底层最高效的操作方式之一。Java中支持的位运算符包括：


| 运算符| 名称	| 描述	| 示例（二进制）| 
| --- | --- | --- | --- |
| `&`	| 按位与	| 两数对应位均为1时结果为1	| 1010 & 1100 = 1000| 
| `\|`	| 按位或	| 两数对应位任一为1时结果为1	| 1010 | 1100 = 1110| 
| `^`	| 按位异或	| 两数对应位不同时结果为1	| 1010 ^ 1100 = 0110| 
| `~`	| 按位取反	| 单目运算符，所有位取反	| ~1010 = 0101（补码）| 
| `<<`	| 左移	| 左移指定位数，低位补0	| 1010 << 2 = 101000| 
| `>>`	| 算术右移	| 右移指定位数，高位补符号位	| 1010 >> 2 = 1110| 
| `>>>`	| 逻辑右移	| 右移指定位数，高位补0	| 1010 >>> 2 = 0010| 

#### 示例代码

**位运算的用法**
```java
// 位运算符
int c = 0b1010; // 10（二进制）
int d = 0b0110; // 6（二进制）
System.out.println("\n----- 位运算符 -----");
System.out.println("c & d : " + (c & d)); // AND → 0010 → 2
System.out.println("c | d : " + (c | d)); // OR → 1110 → 14
System.out.println("c ^ d : " + (c ^ d)); // XOR → 1100 → 12
System.out.println("~c : " + (~c)); // 补码 → -11（十进制）
System.out.println("c << 2 : " + (c << 2)); // 左移2位 → 40
System.out.println("c >> 1 : " + (c >> 1)); // 右移1位 → 5
System.out.println("c >>> 1 : " + (c >>> 1)); // 无符号右移 → 5
print(1);
print(0);
print(-1);

// 输出二进制
static void print(int num){
 for (int i = 31; i >= 0; i--) {
 System.out.print((num & (1 << i)) == 0 ? "0" : "1");
 }
 System.out.println();
}

```

**权限控制（位掩码）**
```java
public class PermissionSystem {
 // 权限标志位定义
 public static final int READ = 1 << 0; // 0001
 public static final int WRITE = 1 << 1; // 0010
 public static final int EXECUTE = 1 << 2; // 0100

 private int permissions = 0; // 初始无权限

 // 添加权限
 public void addPermission(int perm) {
 permissions |= perm;
 }

 // 移除权限
 public void removePermission(int perm) {
 permissions &= ~perm;
 }

 // 检查权限
 public boolean hasPermission(int perm) {
 return (permissions & perm) != 0;
 }

 public static void main(String[] args) {
 PermissionSystem user = new PermissionSystem();
 user.addPermission(READ | WRITE);
 System.out.println(user.hasPermission(READ)); // true
 System.out.println(user.hasPermission(EXECUTE)); // false
 }
}
```

**交换变量值**
```java
int a = 5, b = 3;
a = a ^ b; // a = 5 ^ 3 = 6
b = a ^ b; // b = 6 ^ 3 = 5
a = a ^ b; // a = 6 ^ 5 = 3
System.out.println(a + ", " + b); // 3, 5
```

#### 位运算实际应用场景

1. 性能优化
- 用位运算替代乘除法：x << 1 等价于 x * 2
- 快速判断奇偶性：(x & 1) == 0

2. 数据压缩
- 将多个布尔值压缩到一个整型变量中（如权限系统）

3. 加密算法
- 异或加密：data ^ key

4. 位图算法（BitMap）
- 海量数据去重与排序（如处理10亿个不重复整数）

:::info{title="相关信息"}
想了想，还是将位运算部分放到了常数项模块中，毕竟在算法的过程中，涉及到常数项时间的极致优化、代码写的如何高大上，都离不开位运算，对于本模块，学好位运算才是实操的基石。
:::

## 面试、比赛、刷题中，一个问题的最优解是什么意思？

一般情况下，认为解决一个问题的算法流程，在时间复杂度的指标上，一定要尽可能的低，先满足了时间复杂度最低这个指标之后，使用最少的空间的算法流程，叫这个问题的最优解。

一般说起最优解都是忽略掉常数项这个因素的，因为这个因素只决定了实现层次的优化和考虑，而和怎么解决整个问题的思想无关。


## 复杂度的估算

1. 算法的过程，和具体的语言是无关的。
2. 想分析一个算法流程的时间复杂度的前提，是对该流程非常熟悉
3. 一定要确保在拆分算法流程时，拆分出来的所有行为都是常数时间的操作。这意味着你写算法时，对自己的用过的每一个系统api，都非常的熟悉。否则会影响你对时间复杂度的估算。

算法-理论基础

算法-数据结构基础2

学习了这么长时间的数据结构与算法，通过博客记录下个人的理解与总结，学习过程中多加思考，结合Java集合体系中的结构，思考换做自己要如何实现




# 数据结构

数据结构是算法的基石，只有掌握了数据结构，才能实现各种奇思妙想的算法

**基本概念**

数据结构整体分为线性结构、非线性结构的、散列表等，从物理存储的角度上来说，数据结构又分为物理结构和逻辑结构，物理结构只有数组、链表两种方式，逻辑结构基于数组、链表衍生出来的结构

![image.png](/static/img/7ccb49ea04934450db65bb7738b0b7bc.image.webp)

:::tip{title="重点掌握"}
将上图牢记于心，在脑海中形成自己对数据结构概念理解的轮廓，所有的数据结构都可以基于**物理结构**（也就是数组、链表）进行实现，无非就是逻辑结构上贴合顺序存储方式或者是链式存储方式。
:::

# 线性结构
线性结构是最简单的结构，其中的数据元素之间存在一种线性的关系，可以理解为是一种一维结构。
线性结构可以分为以下几种

## 数组
数组（array），是Java最基础常用的结构，数组中存储的称为元素。

**特点：**
- 数组创建以后，大小固定，是不可变的。 
- 数组中的元素在内存中是连续存储的，天然有序。 
- 每个元素对应着一个下标，可通过下标索引值快速定位到元素。 

:::info{title="相关信息"}
在java中，最经典的莫过于ArrayList的实现，底层使用数组结构，查询、修改效率高，对于插入数据超过数组长度时进行动态扩容，删除中间元素时对元素进行迁移，有兴趣可以阅读下源码
:::


## 链表
链表（Linked list）是一种链式结构，链表中的数据称为节点，每个节点数据中包含下一个节点的数据指针，一个链表由多个节点组成。

**特点：**
- 链表的长度可以动态改变，长度没有限制。 
- 链表中的节点可以在内存中的任意位置，非连续存储。 
- 通过指针来导航和访问链表中的元素。 

![image.png](https://blog.liushigong.cn/static/img/9dc99e421f99e5bfaa25c6bbbdc2b40d.image.webp)

根据以上特点，实现一个单向链表

```java
public class ListNode {
 Object val;
 ListNode next;

 ListNode() {
 }

 ListNode(Object val) {
 this.val = val;
 }

 ListNode(Object val, ListNode next) {
 this.val = val;
 this.next = next;
 }
}
```

:::info{title="相关信息"}
链表的实现分为多种，以上只是单向链表的实现，还存在双向链表，还有单向/双向循环链表，本质就是节点中存在一个指向下一节点的引用与上一节点的引用，即为双向，循环链表的本质就是尾节点的下一个节点从指向null，变成指向头节点，而头节点的上一节点引用从null，变成了指向尾节点
:::


**数组与链表对比**

数组与链表本身既是物理结构，同时也是逻辑结构，他们的优势各不相同 
数组适用于读多写少的场景 
链表适用于频繁插入与删除的场景 
**在Java中，经常把集合ArrayList 与 LinkedList 进行对比，本质对比的就是底层上不同结构的实现**</scan>

![image.png](/static/img/484d6211c50d74384e415810979fa998.image.webp)


## 栈

栈是一种特殊的线性数据结构，支持两种主要操作：压栈（push）和弹栈（pop），遵循先进后出（LIFO, Last In First Out）的原则。

**实现方式：**

数组：使用数组的一端作为栈顶，当需要压栈或出栈时，只需更新栈顶指针。

![image.png](/static/img/6ceb0411f017b24fe7fe6135b00fa926.image.webp)

```java
public class ArrayStack<T> {
 private static final int DEFAULT_CAPACITY = 10;
 private Object[] elements;
 private int top; // 栈顶指针

 public ArrayStack() {
 elements = new Object[DEFAULT_CAPACITY];
 top = -1; // 初始化为空栈
 }

 // 入栈操作
 public void push(T item) {
 if (top == elements.length - 1) {
 resize(); // 动态扩容
 }
 elements[++top] = item;
 }

 // 出栈操作
 public T pop() {
 if (isEmpty()) {
 throw new EmptyStackException();
 }
 T item = (T) elements[top];
 elements[top--] = null; // 帮助垃圾回收
 return item;
 }

 // 查看栈顶元素
 public T peek() {
 if (isEmpty()) {
 throw new EmptyStackException();
 }
 return (T) elements[top];
 }

 // 判断栈是否为空
 public boolean isEmpty() {
 return top == -1;
 }

 // 获取栈大小
 public int size() {
 return top + 1;
 }

 // 动态扩容方法
 private void resize() {
 int newSize = elements.length * 2;
 Object[] newArray = new Object[newSize];
 System.arraycopy(elements, 0, newArray, 0, elements.length);
 elements = newArray;
 }
}
```

链表：使用单向链表的头部作为栈顶，新元素总是添加到头部，出栈也是从头节点开始。

![image.png](/static/img/a259904c2ca8301cd587fbda5f387b42.image.webp)

```java
public class LinkedListStack<T> {
 // 链表节点定义
 private static class Node<T> {
 T data;
 Node<T> next;

 Node(T data) {
 this.data = data;
 this.next = null;
 }
 }

 private Node<T> top; // 栈顶节点
 private int size; // 栈大小

 public LinkedListStack() {
 top = null;
 size = 0;
 }

 // 入栈操作
 public void push(T item) {
 Node<T> newNode = new Node<>(item);
 newNode.next = top; // 新节点指向旧栈顶
 top = newNode; // 更新栈顶指针
 size++;
 }

 // 出栈操作
 public T pop() {
 if (isEmpty()) {
 throw new EmptyStackException();
 }
 T item = top.data;
 top = top.next; // 栈顶指针下移
 size--;
 return item;
 }

 // 查看栈顶元素
 public T peek() {
 if (isEmpty()) {
 throw new EmptyStackException();
 }
 return top.data;
 }

 // 判断栈是否为空
 public boolean isEmpty() {
 return top == null;
 }

 // 获取栈大小
 public int size() {
 return size;
 }
}
```

:::info{title="相关信息"}
栈结构更多的体现在历史的回溯上，在Java中，栈结构是我们接触的数据结构中最多的一种，我们常说的异常堆栈信息，就是使用栈，方法之间的调用都是通过栈来进行存储的。
:::


## 队列
队列是一种只允许在一端进行插入操作，在另一端进行删除操作的线性数据结构，遵循先进先出（FIFO, First In First Out）的原则。

**实现方式：**

数组：使用数组实现 **循环队列**，通过调整指针来模拟循环，从而提高空间利用率。

![image.png](/static/img/ad51c27bf9413a1192c3dc3f29acce14.image.webp)

```java
public class ArrayQueue<E> extends AbstractQueue<E> {
 private static final int DEFAULT_CAPACITY = 10;
 private Object[] elements;
 private int head; // 队列头指针
 private int tail; // 队列尾指针
 private int size; // 当前元素数量

 public ArrayQueue() {
 elements = new Object[DEFAULT_CAPACITY];
 head = 0;
 tail = 0;
 size = 0;
 }

 // 入队操作 (队列满时自动扩容)
 @Override
 public boolean offer(E e) {
 if (size == elements.length) {
 resize();
 }
 elements[tail] = e;
 tail = (tail + 1) % elements.length;
 size++;
 return true;
 }

 // 出队操作
 @Override
 public E poll() {
 if (size == 0) return null;
 E element = (E) elements[head];
 elements[head] = null; // 帮助垃圾回收
 head = (head + 1) % elements.length;
 size--;
 return element;
 }

 // 查看队首元素
 @Override
 public E peek() {
 return size == 0 ? null : (E) elements[head];
 }

 // 队列大小
 @Override
 public int size() {
 return size;
 }

 // 动态扩容方法
 private void resize() {
 int newCapacity = elements.length * 2;
 Object[] newArray = new Object[newCapacity];
 // 将元素复制到新数组的连续位置
 if (head < tail) {
 System.arraycopy(elements, head, newArray, 0, size);
 } else {
 System.arraycopy(elements, head, newArray, 0, elements.length - head);
 System.arraycopy(elements, 0, newArray, elements.length - head, tail);
 }
 elements = newArray;
 head = 0;
 tail = size;
 }

 // 迭代器实现（简化版）
 @Override
 public Iterator<E> iterator() {
 return new Iterator<E>() {
 private int cursor = 0;

 @Override
 public boolean hasNext() {
 return cursor < size;
 }

 @Override
 public E next() {
 if (!hasNext()) throw new NoSuchElementException();
 return (E) elements[(head + cursor++) % elements.length];
 }
 };
 }

 // 清空队列
 @Override
 public void clear() {
 Arrays.fill(elements, null);
 head = 0;
 tail = 0;
 size = 0;
 }
}
```

链表：使用单向链表的头部和尾部作为队列的两端

![image.png](/static/img/4269f5739478e3b897f8f7ef3343f485.image.webp)

```java
public class LinkedQueue<E> extends AbstractQueue<E> {
 // 链表节点定义
 private static class Node<E> {
 E data;
 Node<E> next;

 Node(E data) {
 this.data = data;
 this.next = null;
 }
 }

 private Node<E> head; // 队列头指针
 private Node<E> tail; // 队列尾指针
 private int size; // 队列大小

 public LinkedQueue() {
 head = null;
 tail = null;
 size = 0;
 }

 // 入队操作
 @Override
 public boolean offer(E e) {
 Node<E> newNode = new Node<>(e);
 if (tail == null) {
 head = tail = newNode;
 } else {
 tail.next = newNode;
 tail = newNode;
 }
 size++;
 return true;
 }

 // 出队操作
 @Override
 public E poll() {
 if (size == 0) return null;
 E element = head.data;
 head = head.next;
 if (head == null) {
 tail = null;
 }
 size--;
 return element;
 }

 // 查看队首元素
 @Override
 public E peek() {
 return size == 0 ? null : head.data;
 }

 // 队列大小
 @Override
 public int size() {
 return size;
 }

 // 迭代器实现
 @Override
 public Iterator<E> iterator() {
 return new Iterator<E>() {
 private Node<E> current = head;

 @Override
 public boolean hasNext() {
 return current != null;
 }

 @Override
 public E next() {
 if (!hasNext()) throw new NoSuchElementException();
 E data = current.data;
 current = current.next;
 return data;
 }
 };
 }

 // 清空队列
 @Override
 public void clear() {
 head = null;
 tail = null;
 size = 0;
 }
}
```

:::info{title="相关信息"}
队列还有一些其他类型：优先队列、双端队列 

优先队列：根据优先级进行出队，谁的优先级高谁先出队，其本质是在二叉堆的基础上进行实现。

![image.png](/static/img/18e628a6bbcfece03603e62816a9da0c.image.webp)

双端队列：采用双向链表结构，可以从头部入队出队，也可以从尾部入队出队

![image.png](/static/img/c9e459d8597e37a191c3c5121e19a7d4.image.webp)

:::

## 哈希表
哈希表（hash table）也叫做散列表，这种数据结构提供了键（Key）与值（Value）的映射关系。只要给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1).

### 实现原理

哈希表本质就是一个数组，Value就是数组中的数据，而Key一般是字符串，通过哈希函数算法将Key转换成数组的索引

### 哈希冲突

由于数组的长度是有限的，如果插入的Value值越来越多时，不同的Key通过哈希函数计算出来的索引下标可能会相同，这就是哈希冲突也叫做哈希碰撞

哈希冲突时无可避免的，解决的方式有很多种，最常用的是开放寻址法、链表法。

**开放寻址法**

开放寻址法的思路很简单，就是当Key通过哈希函数计算出来的索引下标位置存在数据时，就往后移一位看是否存在数据，直到找到为空的下标位置进行存储。

**链表法**

哈希表中的数组不仅是一个Enrty，还是链表的头节点。每个Enrty对象都通过next指针指向下一个Entry节点，当新来的Entry的索引下标存在数据冲突时，则将当前Entry插入到链表的尾部即可。

![image.png](/static/img/7c34b840b5139c3e90dcbba773b7082b.image.webp)

当读取数据的时，根据当前哈希函数计算的索引位置，找到链表的头节点，然后从链表中找到Key对应的Enrty。

:::warning{title="思考？当链表过长时，读取效率下降如何处理"}
在极端情况下，如果很多键都映射到同一个桶（bucket），链表会变得很长，导致查询效率从O(1)退化为O(n)，性能下降明显。

回想下 `HashMap` 的源码实现，看下 `HashMap` 在 JDK1.8 中是如何优化链表过长问题的。

**HashMap 的优化：** 

到了Java 8，HashMap 引入了红黑树来优化这个问题。当链表的长度超过一定阈值时，链表会被转换成红黑树，这样查询的时间复杂度可以维持在O(log n)，比链表的O(n)要好很多。

当链表长度超过默认阈值8，且数组长度大于等于64时，才会将链表转换为红黑树。如果数组长度小于64，即使链表长度超过8，HashMap会选择先进行数组扩容，而不是立即转换结构。这是因为扩容可以减少哈希碰撞的概率，可能比转换为树更有效。

另外，红黑树的结构相比链表，虽然查询效率高，但插入和删除操作更复杂，需要维护树的平衡，所以在节点较少时，链表的性能可能更好。因此，HashMap在节点减少到6时会转换回链表，这样可以避免在频繁插入和删除时反复转换带来的性能损耗。

总结一下，HashMap解决链表过长的问题主要通过两个方法：一是当链表长度超过阈值且数组容量足够大时，将链表转为红黑树；二是通过扩容数组来减少哈希碰撞，从而间接减少链表长度。这两种方法结合起来，保证了HashMap在大多数情况下的高效性能。
:::

算法-数据结构基础1

baidu-site-verification

本人自己的博客，对工作与学习过程中的总结、一些场景设计的实现方案、遇到过的疑难问题与解决、以及面试总结等。