时间复杂度

一、时间复杂度是什么？

时间复杂度（Time Complexity） 描述算法运行时间随输入规模 n 增长的 增长趋势。
它不计算具体时间，而是用 大 O 符号（Big O Notation） 表示算法在最坏情况下的时间消耗。

二、常见时间复杂度对比

时间复杂度	名称	示例算法或操作	增长趋势
O(1)	常数时间	数组索引访问、哈希表查询	不随 n 增长变化
O(log n)	对数时间	二分查找、平衡二叉搜索树操作	增长极缓慢
O(n)	线性时间	遍历数组、链表	与 n 成正比增长
O(n log n)	线性对数时间	快速排序、归并排序、堆排序	比 O(n) 稍快，但慢于 O(n²)
O(n²)	平方时间	冒泡排序、选择排序、插入排序	随 n² 增长
O(2ⁿ)	指数时间	穷举所有子集、斐波那契递归实现	急剧增长，不可接受

三、如何计算时间复杂度？

1. 忽略常数项和低阶项

规则：仅保留最高阶项，并省略系数。
- 例如：T(n) = 3n² + 2n + 5 → O(n²)

2. 常见代码结构的时间复杂度

单层循环

for (int i = 0; i < n; i++) { ... }  // O(n)

嵌套循环

for (int i = 0; i < n; i++) {        // O(n²)
    for (int j = 0; j < n; j++) { ... }
}

分治递归

void mergeSort(int[] arr, int l, int r) {  // O(n log n)
    if (l < r) {
        int mid = (l + r) / 2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
}

3. 递归算法的时间复杂度

公式：递归深度 × 每层操作次数
- 示例：二分查找（每次递归规模减半）
```
T(n) = T(n/2) + O(1) → O(log n)
```

四、最好、最坏、平均时间复杂度

1. 最好时间复杂度（Best Case）

算法在 最优输入情况 下的时间复杂度。
- 示例：插入排序在数组已有序时，时间复杂度为 O(n)。

2. 最坏时间复杂度（Worst Case）

算法在 最差输入情况 下的时间复杂度。
- 示例：快速排序在最坏情况下（数组已有序），时间复杂度为 O(n²)。

3. 平均时间复杂度（Average Case）

算法在所有可能输入下的 期望运行时间。
- 示例：快速排序的平均时间复杂度为 O(n log n)。

五、常见误区

O(n) 不一定比 O(1) 慢：当 n 很小时，O(n) 可能更快（比如 n=5）。
相同时间复杂度，性能可能不同：比如同为 O(n²)，插入排序常数项通常小于冒泡排序。
时间复杂度 ≠ 实际运行时间：实际时间受硬件、编程语言、代码优化等因素影响。

六、实战应用

1.选择排序算法

小规模数据（n ≤ 1000）：插入排序（O(n²)）可能更快。
大规模数据（n > 10000）：优先使用归并排序或快速排序（O(n log n)）。

2.优化嵌套循环

将 O(n²) 优化为 O(n log n)：利用哈希表或双指针替代暴力遍历。

枚举算法

枚举算法（又称穷举法）是一种通过遍历所有可能的候选解，逐一验证是否符合条件，从而找到问题正确答案的算法策略。其核心思想是“暴力”检查所有可能性，确保不遗漏任何潜在的解。

模拟算法

模拟算法是通过模拟问题的过程来得到解。模拟的过程通常是根据题目的描述，逐步按照给定的规则操作。与枚举不同的是，模拟关注的是按照步骤执行，而非枚举所有可能的状态。

递归算法

1. 递归的基本思想

递归算法的基本思想是：一个函数通过调用自身来求解问题。每次调用都可以将原问题分解为规模更小、相似的问题，直到达到一个简单的基准情况为止。

递归的核心要素包括：

基准条件：递归的停止条件，防止无限递归。
递归关系：将大问题拆解成小问题，通常通过递归函数的调用实现。

2. 递归算法的结构

一个标准的递归函数通常包含两个部分：

递归的基准条件：这是递归的停止点，当问题足够简单时直接返回结果。
递归的递推公式：即如何将原问题转化为子问题，并递归求解。

3. 递归的示例：计算阶乘

让我们通过一个经典的例子——计算阶乘（factorial）来展示递归算法。

阶乘定义：

0! = 1
n! = n * (n - 1)!

我们可以使用递归来实现阶乘的计算。

public class RecursionExample {
    public static void main(String[] args) {
        int result = factorial(5);  // 计算 5!
        System.out.println(result);  // 输出结果：120
    }

    // 计算阶乘的递归方法
    public static int factorial(int n) {
        // 基准条件
        if (n == 0) {
            return 1;
        }
        // 递归调用
        return n * factorial(n - 1);
    }
}

4. 分析递归算法

在上述代码中，我们定义了一个 factorial 函数，该函数计算给定数字 n 的阶乘。

基准条件：当 n 等于 0 时，函数直接返回 1，结束递归。因为阶乘 0! = 1。
递归调用：当 n > 0 时，函数返回 n * factorial(n - 1)，通过递归调用自身来求解更小的阶乘值。

例如，计算 5! 时，调用流程如下：

factorial(5) 返回 5 * factorial(4)
factorial(4) 返回 4 * factorial(3)
factorial(3) 返回 3 * factorial(2)
factorial(2) 返回 2 * factorial(1)
factorial(1) 返回 1 * factorial(0)
factorial(0) 返回 1（基准条件）

最终，递归过程逐步回溯，最终得到 5 * 4 * 3 * 2 * 1 = 120。

5. 递归的优缺点

优点：

递归算法简洁明了，特别适用于问题本身可以递归分解的场景。
对于树形结构、图遍历、分治法等问题，递归是自然的解决方法。

缺点：

递归调用会消耗较多的栈空间，过深的递归调用可能导致栈溢出。
递归的时间效率较低，某些问题可能会重复计算相同的子问题，导致性能问题。

6. 递归优化

虽然递归非常直观，但有时可能需要优化：

尾递归：某些递归可以通过尾递归优化，避免额外的栈帧开销。
动态规划：对于存在重叠子问题的递归，使用动态规划（记忆化递归或自底向上的动态规划）来避免重复计算。

进制转换

进制转换是指将一个数从一种进制表示转换为另一种进制的过程。在 Java 中，我们经常需要进行不同进制之间的转换，比如将十进制转换成二进制、八进制或十六进制，或者相反。

1. 常见的进制

二进制（Binary）：基数为 2，只包含 0 和 1。
八进制（Octal）：基数为 8，包含 0 到 7。
十进制（Decimal）：基数为 10，包含 0 到 9。
十六进制（Hexadecimal）：基数为 16，包含 0 到 9 和 A 到 F。

2. Java 中的进制转换

Java 提供了多种方式进行进制转换，最常见的是使用 Integer 和 Long 类的内置方法，或者通过手动实现。

2.1 使用 `Integer` 类进行进制转换

Java 提供了 Integer 类中的静态方法来进行进制转换：

Integer.toBinaryString(int)：将整数转换为二进制字符串。
Integer.toOctalString(int)：将整数转换为八进制字符串。
Integer.toHexString(int)：将整数转换为十六进制字符串。

同时，还可以使用 parseInt 方法将其他进制的字符串转换为十进制整数：

Integer.parseInt(String s, int radix)：将字符串 s 按照指定的进制 radix 转换为十进制整数。

2.2 进制转换模板

以下是一个进制转换的通用模板，展示如何将一个十进制数转换为不同的进制。

public class BaseConversion {

    // 十进制转二进制
    public static String decimalToBinary(int number) {
        return Integer.toBinaryString(number);
    }

    // 十进制转八进制
    public static String decimalToOctal(int number) {
        return Integer.toOctalString(number);
    }

    // 十进制转十六进制
    public static String decimalToHexadecimal(int number) {
        return Integer.toHexString(number);
    }

    // 任意进制转十进制
    public static int anyToDecimal(String number, int base) {
        return Integer.parseInt(number, base);
    }

    public static void main(String[] args) {
        int decimalNumber = 255;

        // 十进制转其他进制
        String binary = decimalToBinary(decimalNumber);
        String octal = decimalToOctal(decimalNumber);
        String hexadecimal = decimalToHexadecimal(decimalNumber);

        System.out.println("Decimal: " + decimalNumber);
        System.out.println("Binary: " + binary);
        System.out.println("Octal: " + octal);
        System.out.println("Hexadecimal: " + hexadecimal);

        // 任意进制转十进制
        String binaryString = "11111111";
        int decimalFromBinary = anyToDecimal(binaryString, 2);
        System.out.println("Binary to Decimal: " + decimalFromBinary);
    }
}

3. 代码说明

十进制转其他进制：使用 Integer.toBinaryString()、Integer.toOctalString() 和 Integer.toHexString() 将十进制数转换为二进制、八进制和十六进制字符串。
任意进制转十进制：使用 Integer.parseInt(String s, int radix) 将给定进制的字符串转换为十进制数。radix 参数指定进制（例如，二进制是 2，八进制是 8，十六进制是 16）。

4. 示例输出

对于输入的十进制数 255，该程序将输出：

Decimal: 255
Binary: 11111111
Octal: 377
Hexadecimal: ff
Binary to Decimal: 255

5. 手动实现进制转换

如果需要自己实现进制转换，可以通过不断地除以目标进制，并将余数保留来实现。

public class ManualBaseConversion {

    // 手动实现十进制转任意进制
    public static String decimalToBase(int number, int base) {
        // 边界条件：如果数字为 0，直接返回 "0"
        if (number == 0) {
            return "0";
        }

        StringBuilder result = new StringBuilder();
        char[] digits = "0123456789ABCDEF".toCharArray();  // 用于表示 0-15 的字符

        while (number > 0) {
            int remainder = number % base;
            result.insert(0, digits[remainder]);  // 将余数对应的字符插入到字符串的最前面
            number = number / base;  // 继续除以目标进制
        }

        return result.toString();
    }

    public static void main(String[] args) {
        int decimalNumber = 255;
        
        // 转换为不同的进制
        String binary = decimalToBase(decimalNumber, 2);   // 二进制
        String octal = decimalToBase(decimalNumber, 8);    // 八进制
        String hexadecimal = decimalToBase(decimalNumber, 16); // 十六进制

        System.out.println("Decimal: " + decimalNumber);
        System.out.println("Binary: " + binary);
        System.out.println("Octal: " + octal);
        System.out.println("Hexadecimal: " + hexadecimal);
    }
}

代码解析：

decimalToBase(int number, int base)

：该方法接受两个参数：
```
number
```
（要转换的十进制数）和
```
base
```
（目标进制）。我们通过不断取余和除法，将十进制数转换为目标进制。
- 使用 digits 数组存储从 0 到 15 的字符（0-9 和 A-F），这样就可以表示十六进制中的字母。
- 通过 number % base 获取当前位的余数，然后用余数索引 digits 数组来获取对应的字符。
- 余数对应的字符会被插入到 result 字符串的最前面，这样可以得到从高位到低位的正确结果。
边界条件：当 number 为 0 时，直接返回 "0"，这是因为任何进制中，数字 0 都是 "0"。

示例输出：

对于输入的十进制数 255，程序将输出：

Decimal: 255
Binary: 11111111
Octal: 377
Hexadecimal: FF

前缀和算法

前缀和（Prefix Sum）是一种常用的优化技巧，特别适用于求解区间和相关问题。在给定一个数组时，前缀和是指数组中某个位置之前（包括该位置）的所有元素的和。使用前缀和可以将某些区间和的计算复杂度从 O(n) 降低到 O(1)，从而提高程序效率。

1. 前缀和的定义

给定一个数组 arr，前缀和数组 prefix_sum 的定义如下：

sum[i] 表示数组 arr 中从下标 0 到下标 i 的元素和，即： $$ sum[i]=arr[0]+arr[1]+...+arr[i] $$

其中，sum[0] = arr[0]，并且可以通过动态计算前缀和数组的元素来避免重复计算区间和。

2. 使用前缀和算法求区间和

在得到前缀和数组后，可以在 O(1) 的时间内计算任意区间的和。具体来说，给定区间 [l, r] 的和可以通过以下公式计算： $$ sum(l,r)=sum[r]−sum[l−1] $$ 如果 l == 0，则区间和就是 sum[r]。

3. 前缀和的计算模板

前缀和算法的核心是预处理出前缀和数组，然后在常数时间内查询区间和。以下是一个标准的前缀和算法模板：

public class PrefixSum {

    // 计算前缀和
    public static int[] calculatePrefixSum(int[] arr) {
        int n = arr.length;
        int[] prefixSum = new int[n];

        // 初始化前缀和的第一个元素
        prefixSum[0] = arr[0];

        // 计算前缀和数组
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }

        return prefixSum;
    }

    // 查询区间 [l, r] 的和
    public static int query(int[] prefixSum, int l, int r) {
        if (l == 0) {
            return prefixSum[r];  // 从 0 到 r 的和
        }
        return prefixSum[r] - prefixSum[l - 1];  // 从 l 到 r 的和
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};

        // 计算前缀和
        int[] prefixSum = calculatePrefixSum(arr);

        // 查询区间 [1, 3] 的和
        int sum = query(prefixSum, 1, 3);
        System.out.println("Sum of range [1, 3]: " + sum);  // 输出 9 (2 + 3 + 4)

        // 查询区间 [0, 2] 的和
        int sum2 = query(prefixSum, 0, 2);
        System.out.println("Sum of range [0, 2]: " + sum2);  // 输出 6 (1 + 2 + 3)
    }
}

代码解释：

calculatePrefixSum：这个方法计算并返回一个前缀和数组。初始化时，prefixSum[0] = arr[0]，然后通过迭代计算后续的前缀和，prefixSum[i] = prefixSum[i-1] + arr[i]。
query：这个方法根据前缀和数组来查询区间和。对于区间 [l, r]，如果 l == 0，直接返回 prefixSum[r]，否则返回 prefixSum[r] - prefixSum[l-1]。

4. 时间复杂度

前缀和数组的计算：O(n)，其中 n 是数组的长度。计算过程只需要遍历一次原数组。
查询区间和：O(1)，因为查询只需要访问前缀和数组的两个元素并进行减法操作。

5. 前缀和的应用场景

区间和查询：如上例所示，前缀和常用于处理频繁的区间和查询，尤其在数组很大的时候，能够有效提高查询速度。
矩阵区域和查询：可以通过二维前缀和数组来实现矩阵区域的快速求和。
最小子数组和问题：有时，前缀和也可用于处理数组中的最小子数组和等问题。

6. 变种：二维前缀和

如果数组是二维的，可以扩展前缀和算法来计算任意矩阵区域的和。例如，对于一个二维矩阵，可以计算出二维前缀和数组 prefix_sum[i][j]，使得它可以在 O(1) 的时间内查询任意矩形区域的和。

public class TwoDimPrefixSum {

    // 计算二维前缀和
    public static int[][] calculatePrefixSum(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] prefixSum = new int[m][n];

        // 初始化前缀和的第一个元素
        prefixSum[0][0] = matrix[0][0];

        // 第一行
        for (int i = 1; i < n; i++) {
            prefixSum[0][i] = prefixSum[0][i - 1] + matrix[0][i];
        }

        // 第一列
        for (int i = 1; i < m; i++) {
            prefixSum[i][0] = prefixSum[i - 1][0] + matrix[i][0];
        }

        // 计算其他位置的前缀和
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                prefixSum[i][j] = matrix[i][j] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
            }
        }

        return prefixSum;
    }

    // 查询矩阵中子矩形区域的和
    public static int query(int[][] prefixSum, int x1, int y1, int x2, int y2) {
        int total = prefixSum[x2][y2];
        if (x1 > 0) total -= prefixSum[x1 - 1][y2];
        if (y1 > 0) total -= prefixSum[x2][y1 - 1];
        if (x1 > 0 && y1 > 0) total += prefixSum[x1 - 1][y1 - 1];
        return total;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        int[][] prefixSum = calculatePrefixSum(matrix);

        // 查询矩阵中 (1,1) 到 (2,2) 的和
        System.out.println(query(prefixSum, 1, 1, 2, 2));  // 输出 28 (5+6+8+9)
    }
}

总结：

前缀和算法是一种非常高效的算法，用于快速处理区间和问题。通过预处理前缀和数组，我们可以将区间和的查询时间从 O(n) 降低到 O(1)。这个技巧不仅适用于一维数组，也可以扩展到二维数组等更复杂的数据结构。

差分算法

差分算法（Difference Array）是一种常用的优化技术，通常用于处理区间更新的问题。差分算法的核心思想是通过记录相邻元素之间的差异，来实现对数组区间的快速修改。它通过将数组的每个更新操作转换为对数组差分的修改，减少了更新操作的时间复杂度，从而提高了效率。

1. 基本思想

差分算法的关键在于，将原数组的值表示为相邻元素之间的差值。通过这种方式，区间的更新可以在常数时间内完成。

步骤：

创建差分数组：对于原始数组 arr，差分数组 diff 的定义如下：
- diff[0] = arr[0]
- diff[i] = arr[i] - arr[i-1]（对于 i > 0）
区间更新：如果我们需要将原数组的区间 [l, r] 中的所有元素加上一个常数 x，可以通过修改差分数组来完成：
- diff[l] += x （区间左端点增加）
- diff[r + 1] -= x （区间右端点的下一位置减去相同的值）
恢复原数组：最后，通过累加差分数组来恢复原数组。恢复公式为：
- arr[i] = diff[0] + diff[1] + ... + diff[i]（从差分数组恢复）

2. 差分算法的应用

区间加法：对于一个区间 [l, r]，要给数组中的每个元素加上一个常数 x。通过差分数组，可以在常数时间内实现。
区间赋值：通过差分算法，也可以高效地实现区间赋值操作。

3. 差分算法的模板

以下是一个差分算法的模板，展示如何使用差分数组来高效处理区间更新问题：

public class DifferenceAlgorithm {

    // 差分数组实现区间加法
    public static void applyRangeUpdate(int[] diff, int l, int r, int x) {
        // 区间 [l, r] 中的所有元素加上 x
        diff[l] += x;  // 左端点加 x
        if (r + 1 < diff.length) {
            diff[r + 1] -= x;  // 右端点后一个位置减 x
        }
    }

    // 恢复原数组
    public static int[] restoreArray(int[] diff) {
        int n = diff.length;
        int[] arr = new int[n];
        arr[0] = diff[0];

        for (int i = 1; i < n; i++) {
            arr[i] = arr[i - 1] + diff[i];
        }

        return arr;
    }

    public static void main(String[] args) {
        // 原数组
        int[] arr = {1, 2, 3, 4, 5};
        int n = arr.length;

        // 差分数组初始化
        int[] diff = new int[n];
        diff[0] = arr[0];

        for (int i = 1; i < n; i++) {
            diff[i] = arr[i] - arr[i - 1];
        }

        // 区间 [1, 3] 的元素加 2
        applyRangeUpdate(diff, 1, 3, 2);

        // 恢复数组
        int[] updatedArr = restoreArray(diff);

        // 输出更新后的数组
        System.out.println("Updated Array:");
        for (int num : updatedArr) {
            System.out.print(num + " ");
        }
        // 输出结果：[1 4 5 6 5]
    }
}

代码解析

applyRangeUpdate(int[] diff, int l, int r, int x)：该方法用于在差分数组上执行区间更新。它将区间 [l, r] 的每个元素增加 x。通过在 diff[l] 增加 x 和 diff[r + 1] 减去 x，我们可以将更新转化为差分数组的操作。
restoreArray(int[] diff)：该方法通过累加差分数组来恢复原数组的值。通过将差分数组中的每个元素加到之前的结果中，最终恢复出原始的数组。
main 方法：
- 初始化一个数组 arr。
- 计算并存储 arr 的差分数组。
- 在差分数组中应用区间更新。
- 恢复并输出更新后的数组。

4. 时间复杂度

初始化差分数组：O(n)，通过遍历原数组一次来计算差分数组。
区间更新：O(1)，通过修改差分数组的两个元素实现区间更新。
恢复原数组：O(n)，通过累加差分数组来恢复原数组。

总体时间复杂度：O(n)（初始化和恢复原数组） + O(1)（每次区间更新）。

5. 差分算法的应用场景

区间更新问题：当数组需要频繁进行区间更新时（例如区间加法、区间赋值等），差分算法可以大幅度减少时间复杂度，特别是在需要对区间进行多次更新时。
前缀和的变种：差分算法可以看作是前缀和的一种变形，适用于那些需要频繁更新数组区间的场景。

6. 总结

差分算法通过将数组更新转化为差分的形式，使得区间更新的时间复杂度降低到 O(1)。它特别适用于需要频繁进行区间加法或者区间修改的场景，能够有效提高效率。

离散化法简介

离散化法（Discretization）是一种常用于处理区间或数值范围问题的技术，尤其是在处理大规模数据时。它的核心思想是将连续的数值范围或区间映射到一个有限的、离散的集合中，以便于进一步的处理。离散化的应用在许多问题中都非常常见，尤其是在处理动态区间、区间查询、坐标压缩等问题时，能够大大减少计算的复杂度和空间消耗。

1. 离散化的基本思想

离散化的基本思路是将数据中的某些值（通常是连续值）映射到一个更紧凑的、有限的整数范围内。通过将一系列的值映射到一个较小的范围，可以方便地使用数组、树、线段树等数据结构进行后续的处理。

例如，对于一组值 [10, 100, 200, 500]，我们可以将其离散化为 [0, 1, 2, 3]。这个过程帮助我们把一系列不连续的数值转化为一个连续的整数区间，从而减少数据的复杂性。

2. 离散化的步骤

收集所有待离散化的值：首先，收集所有需要离散化的数值，通常是一个区间或数组。
排序：对收集到的数值进行排序，以便于为每个数值分配一个唯一的整数编号。
映射到离散值：将排序后的数值映射到连续的整数区间。例如，最小值映射为 0，第二小值映射为 1，以此类推。
更新原数据：用映射后的离散值替换原数据中的数值，完成离散化操作。

3. 离散化的常见应用

坐标压缩：例如，二维平面上的坐标对，可以通过离散化将坐标转化为整数，方便在数据结构中进行存储和查询。
区间查询问题：在处理区间查询时，可以通过离散化将区间范围压缩，从而优化查询过程。
区间更新问题：通过离散化将连续的区间映射为离散的索引，可以高效地使用线段树、树状数组等数据结构进行区间更新和查询。
离散化频率：对于频繁出现的数值，通过离散化可以减少重复计算，降低时间复杂度。

4. 离散化法的模板

以下是一个标准的离散化法的模板，展示如何将一个数组中的元素离散化：

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Discretization {

    // 离散化方法
    public static int[] discretize(int[] arr) {
        // Step 1: 复制原数组，避免修改原始数组
        int[] sortedArr = arr.clone();

        // Step 2: 对数组进行排序
        Arrays.sort(sortedArr);

        // Step 3: 创建一个映射，将数值映射到离散值
        Map<Integer, Integer> mapping = new HashMap<>();
        int index = 0;
        for (int value : sortedArr) {
            if (!mapping.containsKey(value)) {
                mapping.put(value, index++);
            }
        }

        // Step 4: 将原数组中的数值替换为离散值
        int[] result = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            result[i] = mapping.get(arr[i]);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {100, 200, 50, 100, 150};

        // 离散化
        int[] discretizedArr = discretize(arr);

        // 输出离散化后的数组
        System.out.println("Original Array: " + Arrays.toString(arr));
        System.out.println("Discretized Array: " + Arrays.toString(discretizedArr));
    }
}

代码解析

discretize(int[] arr)：该方法接受一个数组 arr，将其离散化后返回。
- 排序：首先对输入数组进行排序，得到一个有序的数组 sortedArr，这为后续映射到离散值做准备。
- 映射：通过 HashMap 将排序后的每个唯一值与一个离散的整数索引一一对应，确保每个值都得到唯一的映射。
- 替换：最后，将原数组中的每个数值替换为其对应的离散值。
main 方法：
- 在 main 方法中，我们给出了一个数组 arr，然后通过 discretize 方法将该数组离散化，输出离散化后的结果。

示例输出

对于输入数组 [100, 200, 50, 100, 150]，输出会是：

Original Array: [100, 200, 50, 100, 150]
Discretized Array: [1, 3, 0, 1, 2]

离散化后的数组将原始值 [100, 200, 50, 100, 150] 映射为 [1, 3, 0, 1, 2]，其中：

50 被映射为 0，
100 被映射为 1，
150 被映射为 2，
200 被映射为 3。

5.时间复杂度

排序时间复杂度：O(n log n)，排序是离散化过程中的主要耗时操作。
映射时间复杂度：O(n)，我们遍历排序后的数组并为每个值分配一个唯一的离散值。
总时间复杂度：O(n log n)，主要受排序操作的影响。

6. 离散化的应用场景

坐标压缩：在处理坐标或范围问题时，离散化可以有效压缩数据的表示，减少内存消耗。
数据压缩：对于稀疏数据，离散化可以将数据的表示压缩为一个较小的范围，优化存储和查询效率。
区间更新：在处理大量区间更新时，离散化可以将连续区间转化为整数区间，从而减少计算量，优化区间操作。

总结

离散化法是一种通过将连续的数据映射到离散的整数区间来简化问题的技术，尤其适用于区间查询、坐标压缩和大规模数据处理等场景。通过使用离散化，能够有效减少数据的复杂度，并提高后续计算和查询的效率。

贪心算法

贪心算法（Greedy Algorithm）是一种在解决问题时采用局部最优解策略的算法。每一步选择中，贪心算法总是做出当前看来最优的选择，即“贪心地”选择当下最好的选项。贪心算法通常适用于一些具有“最优子结构”性质的问题，其中每个子问题的最优解可以推导出整体问题的最优解。

贪心算法的核心思想是：在求解问题时，做出当前最优的选择，并希望通过一系列的局部最优选择，最终达到全局最优解。

1. 贪心算法的特点

局部最优选择：每一步选择都基于当前情况做出看似最优的选择。
全局最优解：通过局部最优解的选择，最终获得全局最优解（在某些问题中，贪心算法能保证得到最优解，但并非所有问题都能保证）。
无回溯：贪心算法一次选择后，不会回退去尝试其他可能的选择。

2. 贪心算法的步骤

贪心算法的设计过程通常包括以下几个步骤：

问题的描述：清楚地理解问题及其约束条件。
选择标准：设定一个可以根据贪心选择来判断当前局部最优解的标准。
问题分解：将问题分解为子问题，且每个子问题的解能够通过选择局部最优解来得到。
选择策略：在每一步中，选择局部最优解。
验证全局最优性：在某些情况下，需要验证局部最优选择是否能够保证全局最优解。

3. 贪心算法的适用条件

并非所有问题都适合使用贪心算法。贪心算法能得到全局最优解的关键是问题必须满足以下条件：

最优子结构：问题的最优解可以由子问题的最优解推导出来。
贪心选择性质：局部最优解能导出全局最优解，即每次选择的局部最优解能保证最终得到全局最优解。

如果不满足上述条件，贪心算法可能会得到错误的解。

4. 贪心算法的常见应用

活动选择问题：选择一系列互不重叠的活动，使得活动的总数最大化。
背包问题（0/1背包问题的贪心近似解）：对于带有价值和重量的物品，选择一个价值与重量比最大的物品，尽量使背包的总价值最大。
最小生成树：如 Prim 算法和 Kruskal 算法。
哈夫曼编码：一种用于数据压缩的编码方法。
区间调度问题：从多个时间段中选择尽可能多的互不重叠的区间。
硬币问题：找出最少的硬币数量来凑成某个金额（如果币种满足贪心选择性质）。

5. 贪心算法的例子

例：活动选择问题

问题描述：给定一组活动，每个活动有一个开始时间和结束时间。选择尽可能多的互不重叠的活动，使得它们的总数最大。

贪心策略：每次选择结束时间最早的活动。这样可以留下足够的时间给后续活动，最大化可选活动的数量。

代码实现：

import java.util.*;

public class ActivitySelection {

    // 定义活动的类
    static class Activity {
        int start, end;

        public Activity(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    // 贪心算法求解最大活动选择
    public static List<Activity> selectActivities(Activity[] activities) {
        // 按结束时间排序活动
        Arrays.sort(activities, Comparator.comparingInt(a -> a.end));

        List<Activity> result = new ArrayList<>();
        int lastEndTime = -1;

        // 选择活动
        for (Activity activity : activities) {
            // 如果活动的开始时间大于等于上一个活动的结束时间，选择这个活动
            if (activity.start >= lastEndTime) {
                result.add(activity);
                lastEndTime = activity.end;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        // 假设有以下活动
        Activity[] activities = {
            new Activity(1, 3),
            new Activity(2, 5),
            new Activity(4, 7),
            new Activity(6, 8),
            new Activity(5, 9)
        };

        // 选择互不重叠的最大活动集
        List<Activity> selectedActivities = selectActivities(activities);

        // 输出结果
        System.out.println("Selected activities:");
        for (Activity activity : selectedActivities) {
            System.out.println("Start: " + activity.start + ", End: " + activity.end);
        }
    }
}

6. 贪心算法的时间复杂度

排序操作：排序活动所需时间为 O(n log n)，其中 n 为活动的个数。
选择活动：选择活动的操作需要遍历所有活动一次，时间复杂度为 O(n)。

因此，贪心算法在活动选择问题中的总时间复杂度为 O(n log n)。

7. 贪心算法的优缺点

优点：

简单高效：贪心算法通常具有较简单的实现，而且时间复杂度低，适合于大规模数据的处理。
无需回溯：每一步都做出选择后就不再回溯，减少了很多计算量。

缺点：

无法保证最优解：并不是所有问题都能通过贪心算法得到最优解。如果问题不满足“最优子结构”和“贪心选择性质”，贪心算法可能会得到错误的解。
问题建模困难：对于复杂问题，设计贪心策略并非易事，往往需要精确理解问题的结构。

8. 总结

贪心算法是一种非常高效、直观的算法，适用于满足特定条件的问题。它的主要思想是通过选择当前局部最优解来期望得到全局最优解。然而，并不是所有问题都适合使用贪心算法，因此在使用贪心算法时，必须确保问题满足贪心选择性质和最优子结构。

以下是 Java 中 快慢指针 和 对撞指针（左右指针） 的详细解析，包含核心思想、代码实现和典型应用场景：

双指针

一、快慢指针（Fast-Slow Pointers）

核心思想

使用两个指针以 不同速度 遍历链表或数组。
快指针：一次移动多步（如2步）。
慢指针：一次移动一步。
典型应用：检测循环、找中点、找倒数第k个节点。

1. 检测链表是否有环

public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        if (slow == fast) return true; // 快慢指针相遇，存在环
        slow = slow.next;
        fast = fast.next.next;
    }
    return false;
}

关键点：快指针每次走2步，慢指针每次走1步。若有环，快指针会追上慢指针。

2. 找到链表的中间节点

public ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;      // 慢指针走1步
        fast = fast.next.next; // 快指针走2步
    }
    return slow; // 当链表长度为偶数时，返回第二个中间节点
}

关键点：快指针到达末尾时，慢指针正好在中间。

3. 找链表的倒数第k个节点

public ListNode findKthFromEnd(ListNode head, int k) {
    ListNode fast = head;
    ListNode slow = head;
    // 快指针先走k步
    for (int i = 0; i < k; i++) {
        if (fast == null) return null; // 链表长度不足k
        fast = fast.next;
    }
    // 快慢指针同时走，直到快指针到末尾
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

关键点：快指针先走k步，随后同步移动，快指针到末尾时，慢指针指向倒数第k个节点。

二、对撞指针（左右指针，Two Pointers）

核心思想

使用两个指针从 两端向中间移动，处理有序数组或字符串问题。
典型应用：两数之和、反转字符串、回文判断。

1. 两数之和（有序数组）

public int[] twoSum(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++; // 和太小，左指针右移
        } else {
            right--; // 和太大，右指针左移
        }
    }
    return new int[0];
}

关键点：利用有序特性调整指针位置。

2. 反转字符串

public void reverseString(char[] s) {
    int left = 0;
    int right = s.length - 1;
    while (left < right) {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

关键点：交换左右指针指向的字符。

3. 判断回文字符串

public boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        // 跳过非字母数字字符
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
        // 比较字符（忽略大小写）
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

关键点：跳过无效字符后，对称位置字符需相等。

三、对比总结

指针类型	特点	典型场景	时间复杂度
快慢指针	不同速度遍历	链表问题（环、中点）	O(n)
对撞指针	两端向中间移动	有序数组、字符串操作	O(n)

四、注意事项

链表问题：
- 快指针移动时需检查 fast.next != null，避免空指针异常。
数组/字符串问题：
- 处理边界条件（如空数组、越界访问）。
- 对撞指针通常要求数组有序（如两数之和）。

二分查找算法

二分查找是一种在 有序数组 中快速查找目标值的高效算法，通过不断缩小搜索范围将时间复杂度优化到 O(log n)。

二、核心思想

确定搜索区间：初始区间通常为整个数组 [left, right]。
计算中间点：取中点 mid，比较中间值与目标值。
缩小区间：根据比较结果，排除不可能的一半区间。
循环终止：当区间缩小到无法再分时结束。

三、两种模板详解

模板一：左闭右闭区间 `[left, right]`

适用场景

查找 精确值（如目标值是否存在）。
数组元素 无重复 或需要找到任意一个目标值的位置。

代码实现

public int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1; // 右闭
    while (left <= right) {      // 终止条件：left > right
        int mid = left + (right - left) / 2; // 避免溢出
        if (nums[mid] == target) {
            return mid;          // 找到目标
        } else if (nums[mid] < target) {
            left = mid + 1;      // 目标在右半区间 [mid+1, right]
        } else {
            right = mid - 1;     // 目标在左半区间 [left, mid-1]
        }
    }
    return -1; // 未找到
}

关键点

循环条件：left <= right（允许左右相等）。
边界更新：left = mid + 1 或 right = mid - 1。
终止状态：left > right，区间为空。

模板二：左闭右开区间 `[left, right)`

适用场景

查找 左边界 或 右边界（如找第一个/最后一个等于目标的值）。
处理 重复元素 或需要找到边界位置的问题。

代码实现（找左边界）

public int leftBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;     // 右开
    while (left < right) {       // 终止条件：left == right
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid;        // 目标在左半区间 [left, mid)
        } else {
            left = mid + 1;     // 目标在右半区间 [mid+1, right)
        }
    }
    // 检查越界及是否找到目标
    if (left >= nums.length || nums[left] != target) return -1;
    return left;
}

关键点

循环条件：left < right（终止时 left == right）。
边界更新：right = mid 或 left = mid + 1。
终止状态：left == right，此时需额外检查是否找到目标。

四、两种模板对比

特性	模板一（左闭右闭）	模板二（左闭右开）
初始区间	`[0, nums.length-1]`	`[0, nums.length)`
循环条件	`while (left <= right)`	`while (left < right)`
边界更新	`left = mid + 1` 或 `right = mid - 1`	`left = mid + 1` 或 `right = mid`
适用场景	精确值查找	边界查找（左/右边界）
终止状态	`left > right`（区间空）	`left == right`（区间大小为1）

五、常见问题及解决

1. 如何避免死循环？

计算 mid 时统一用 left + (right - left) / 2（向下取整）。
模板二 中若用 mid = (left + right) / 2，需搭配 left = mid + 1 和 right = mid。

2. 如何处理重复元素？

找左边界：当 nums[mid] == target 时继续向左压缩（right = mid）。
找右边界：当 nums[mid] == target 时继续向右压缩（left = mid + 1）。

六、经典例题

1. 搜索旋转排序数组

public int searchRotatedArray(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        // 判断左右哪部分有序
        if (nums[left] <= nums[mid]) { // 左半部分有序
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else { // 右半部分有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

2. 寻找右边界

public int rightBound(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1; // 向右压缩
        } else {
            right = mid;
        }
    }
    // 检查是否找到
    if (left == 0 || nums[left-1] != target) return -1;
    return left - 1;
}

七、总结

模板一：适合精确查找，逻辑简单直接。
模板二：适合边界查找，需注意终止条件和越界检查。
核心技巧：根据问题类型选择合适的模板，并正确处理边界条件。

基础算法

时间复杂度

一、时间复杂度是什么？

二、常见时间复杂度对比

三、如何计算时间复杂度？

1. 忽略常数项和低阶项

2. 常见代码结构的时间复杂度

3. 递归算法的时间复杂度

四、最好、最坏、平均时间复杂度

1. 最好时间复杂度（Best Case）

2. 最坏时间复杂度（Worst Case）

3. 平均时间复杂度（Average Case）

五、常见误区

六、实战应用

1.选择排序算法

2.优化嵌套循环

枚举算法

模拟算法

递归算法

1. 递归的基本思想

2. 递归算法的结构

3. 递归的示例：计算阶乘

4. 分析递归算法

5. 递归的优缺点

6. 递归优化

进制转换

1. 常见的进制

2. Java 中的进制转换

2.1 使用 Integer 类进行进制转换

2.2 进制转换模板

3. 代码说明

4. 示例输出

5. 手动实现进制转换

代码解析：

示例输出：

前缀和算法

1. 前缀和的定义

2. 使用前缀和算法求区间和

3. 前缀和的计算模板

代码解释：

4. 时间复杂度

5. 前缀和的应用场景

6. 变种：二维前缀和

总结：

差分算法

1. 基本思想

2. 差分算法的应用

3. 差分算法的模板

代码解析

4. 时间复杂度

5. 差分算法的应用场景

6. 总结

离散化法简介

1. 离散化的基本思想

2. 离散化的步骤

3. 离散化的常见应用

4. 离散化法的模板

代码解析

示例输出

5.时间复杂度

6. 离散化的应用场景

总结

贪心算法

1. 贪心算法的特点

2. 贪心算法的步骤

3. 贪心算法的适用条件

4. 贪心算法的常见应用

5. 贪心算法的例子

例：活动选择问题

代码实现：

6. 贪心算法的时间复杂度

7. 贪心算法的优缺点

优点：

缺点：

8. 总结

双指针

一、快慢指针（Fast-Slow Pointers）

核心思想

1. 检测链表是否有环

2. 找到链表的中间节点

2.1 使用 `Integer` 类进行进制转换

模板一：左闭右闭区间 `[left, right]`

模板二：左闭右开区间 `[left, right)`