Lesson 13. 时间复杂度，排序和贪心算法

1. 时间复杂度简介

时间复杂度 是衡量算法执行效率的重要指标，它描述了随着输入数据量的增大，算法执行时间的增长速度。时间复杂度通常表示为 O(某个函数)，其中 "O" 表示增长的上限。以下介绍四种常见的时间复杂度：O(1)、O(n)、O(n^2) 和 O(n log n)。

常见的时间复杂度

O(1)：常数时间复杂度
- 操作的执行时间不随输入数据的大小而变化。
- 例子：从数组中获取第 k 个元素。

Java
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2;  // 获取第三个元素（索引从0开始）
        int element = arr[k];  // O(1)
        System.out.println("Element at index " + k + ": " + element);
    }
}

时间复杂度：无论数组大小是多少，获取第 k 个元素所需时间是固定的，属于 O(1)。

O(n)：线性时间复杂度
- 操作的执行时间随着输入数据量线性增长。
- 例子：遍历一个数组。

Java
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int n = arr.length;  // 获取数组的长度
        for (int i = 0; i < n; i++) {  // O(n)
            System.out.println("Element at index " + i + ": " + arr[i]);
        }
    }
}

时间复杂度：遍历整个数组需要的时间与数组的长度 n 成正比，属于 O(n)。

O(n^2)：平方时间复杂度
- 操作的执行时间与输入数据量的平方成正比，常见于双重循环。
- 例子：打印二维数组中每个元素。

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

        for (int i = 0; i < 3; i++) {  // O(n)
            for (int j = 0; j < 3; j++) {  // O(n)
                System.out.println("Element at [" + i + "][" + j + "]: " + arr[i][j]);
            }
        }
    }
}

时间复杂度：双重循环嵌套遍历每个元素，总的执行时间是 n 的平方，属于 O(n^2)。

O(n log n)：常见于排序算法（此章节后半部分会详细讲解）
- 例子：归并排序、快速排序。

Java
import java.util.Arrays;

public class Main {

    // 合并两个子数组
    public static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int[] L = new int[n1];
        int[] R = new int[n2];

        // 将数据复制到临时数组 L 和 R
        for (int i = 0; i < n1; i++)
            L[i] = arr[l + i];
        for (int i = 0; i < n2; i++)
            R[i] = arr[m + 1 + i];

        // 合并临时数组到 arr
        int i = 0, j = 0, k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // 复制剩余的 L 中的元素（如果有）
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // 复制剩余的 R 中的元素（如果有）
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

   // 递归拆分数组
   public static void mergeSort(int[] arr, int l, int r) {
       if (l < r) {
           int m = l + (r - l) / 2;

           // 递归排序两半
           mergeSort(arr, l, m);
           mergeSort(arr, m + 1, r);

           // 合并两个排序好的子数组
           merge(arr, l, m, r);
       }
   }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        int arr_size = arr.length;

        mergeSort(arr, 0, arr_size - 1);

        System.out.println("Sorted array is: " + Arrays.toString(arr));
    }
}

时间复杂度：归并排序通过递归将数组分成更小的部分进行排序，时间复杂度为 O(n log n)。

为什么是 `O(n log n)`?

归并排序是一种 分治算法，我们可以把归并排序的步骤分为两部分：拆分和合并。

1. 拆分过程：递归分解数组

归并排序首先将数组递归地对半拆分，直到每个子数组只剩下一个元素。这个过程类似于构建一棵二叉树，每次将问题的规模减半。

对一个长度为 n 的数组：
- 第一层：1 个长度为 n 的数组
- 第二层：2 个长度为 n/2 的数组
- 第三层：4 个长度为 n/4 的数组
- ...
- 第 log n 层：每个数组的长度是 1，共有 n 个数组

因为每次都对数组进行二分，所以整个递归树的深度是 log n。

2. 合并过程：线性合并

当子数组拆分到最小（每个数组只有一个元素）时，归并排序开始合并这些子数组。合并两个有序数组的时间与它们的长度成正比，也就是说合并两个数组的时间是 O(n)。

在递归树的每一层，所有数组的总长度始终是 n，因此：

第一层：合并一个长度为 n 的数组，时间是 O(n)
第二层：合并两个长度为 n/2 的数组，总时间仍然是 O(n)
第三层：合并四个长度为 n/4 的数组，总时间也是 O(n)

无论有多少个小数组，合并每一层的总时间都是 O(n)。

3. 递归树的层数

拆分的过程最多进行 log n 次（每次将数组对半分）。因此，递归树的深度是 log n，即最多有 log n 层。

总时间复杂度的计算

因为每一层的合并时间都是 O(n)，而整个递归树有 log n 层，所以总的时间复杂度是 O(n) * O(log n) = O(n log n)

为什么不会超过 O(n log n)

有人可能会疑惑：既然我们在递归中反复分裂数组，为什么时间复杂度不会超过 O(n log n) 呢？

每层的合并操作是线性的：虽然递归分裂会产生多个小数组，但每一层中所有数组的总长度仍然是 n。也就是说，每一层合并的时间复杂度始终是 O(n)，不会累积更多复杂度。
递归的深度是 log n：由于每次递归都将数组对半分裂，整个递归过程只会进行 log n 次分裂。因此，递归树的深度是 log n。

最终的时间复杂度是每层的时间 O(n) 乘以递归树的层数 log n，所以总时间复杂度是 O(n log n)。

时间复杂度总结

O(1)：执行时间不受输入规模影响。
O(n)：执行时间随输入规模线性增长。
O(n^2)：执行时间与输入规模的平方成正比，通常发生在嵌套循环中。
O(n log n)：常见于高效的排序算法。

具体实例

考虑一个简单的算法：计算数组中所有元素的和。

Java
public class Main {

    public static int sumArray(int[] arr, int n) {
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += arr[i]; 
        }
        return total;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int n = arr.length;
        System.out.println("Sum of array: " + sumArray(arr, n));
    }
}

步骤分析

确定基本操作：
- 基本操作是 total += arr[i]，这是一种数组元素的加法。
计算基本操作的次数：
- 在最坏情况下，for 循环将执行 n 次（其中 n 是数组 arr 的长度）。
- 因此，基本操作的次数为 n。
使用大 O 表示法：
- 由于循环执行了 n 次，时间复杂度为 O(n)。
考虑最坏情况：
- 无论输入的具体内容如何，只要数组长度为 n，基本操作都会执行 n 次，最坏情况仍为 O(n)。
特殊情况：
- 如果数组为空（长度为 0），for 循环不会执行，但算法的时间复杂度依然为 O(n)，因为我们考虑的是输入的规模。

随堂练习

判断以下代码的时间复杂度

Java
public class Main {

    public static int findMax(int[] arr, int n) {
        int maxNum = arr[0];
        for (int i = 0; i < n; i++) {  // 基本操作
            if (arr[i] > maxNum) {
                maxNum = arr[i];
            }
        }
        return maxNum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 5, 3, 9, 2};
        int n = arr.length;
        System.out.println("Max number: " + findMax(arr, n));
    }
}

解答

第一段代码（findMax 方法）：

基本操作是 if (arr[i] > maxNum)，即在每次循环中进行一次比较操作。
循环执行次数：for 循环从 i = 0 到 i = n - 1，因此在最坏情况下，循环执行 n 次（即数组的长度为 n）。
时间复杂度分析：在每次迭代中，执行一次比较和可能的赋值操作，操作的次数和输入规模 n 成线性关系。因此时间复杂度为 O(n)。

2. 排序算法与应用

排序是程序设计中一个非常基础但重要的操作。它不仅可以让数据按特定顺序排列，还能帮助我们解决许多与数据处理相关的问题。通过排序，我们可以更快地解决找第 K 大元素、合并重叠区间等问题。

适用场景

排序的应用场景非常广泛，尤其是在数据处理中，你会经常遇到需要对数据进行排序的情况：

找出第 K 大元素：通过排序数据，可以很快找出第 K 大（或第 K 小）的元素。
合并区间：当处理多个区间或段时，常常需要先将这些区间按某个维度排序，然后合并它们。
例子：合并日程、任务时间段等数据，解决区间重叠问题。
优化操作：不同的排序算法在面对不同规模的数据时表现各异，因此选择合适的排序算法对于提高程序性能非常重要。

常用技巧

1. 内置排序函数

Java 提供了非常方便的排序函数 Arrays.sort()，用于对数组进行排序。这个方法使用了经过优化的快速排序、归并排序等高效的排序算法。

示例代码：

Java
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {3, 1, 4, 1, 5, 9};  // 定义一个整数数组

        // 使用内置的排序函数对数组进行升序排序
        Arrays.sort(nums);

        // 输出排序后的数组
        System.out.print("Sorted array: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}

说明：

在 Java 中，我们使用 Arrays.sort() 来对数组 nums 进行升序排序。
内置的 Arrays.sort() 非常快捷且高效，适用于大多数情况。

2. 自定义排序

在 Java 中，Comparator 是一个接口，用于定义自定义的排序逻辑。通过实现这个接口，我们可以为集合（如数组、列表等）提供特定的排序规则。

自定义 Comparator

要创建自定义的 Comparator，你可以采用以下两种方法：

方法一：实现 `Comparator` 接口

你可以通过创建一个实现 Comparator 接口的类来定义排序逻辑。

Java
import java.util.Comparator;

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }
}

// 自定义比较器，根据年龄排序
class AgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        return Integer.compare(p1.getAge(), p2.getAge());
    }
}

方法二：使用 Lambda 表达式（Java 8 及以上）

在 Java 8 及以上版本中，你可以使用 Lambda 表达式来简化 Comparator 的实现：

Java
import java.util.Arrays;
import java.util.Comparator;

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }
}

public class Main {
    public static void main(String[] args) {
        Person[] people = {
            new Person("Alice", 30),
            new Person("Bob", 25),
            new Person("Charlie", 35)
        };

        // 使用 Lambda 表达式按年龄排序
        Arrays.sort(people, (p1, p2) -> Integer.compare(p1.getAge(), p2.getAge()));

        // 打印排序后的结果
        for (Person p : people) {
            System.out.println(p.getName() + ": " + p.getAge());
        }
    }
}

多重排序

如果你想要根据多个条件进行排序，可以在 compare 方法中添加额外的逻辑。例如，首先按年龄排序，如果年龄相同，则按名字排序：

Java
Arrays.sort(people, (p1, p2) -> {
    int ageComparison = Integer.compare(p1.getAge(), p2.getAge());
    if (ageComparison != 0) {
        return ageComparison; // 如果年龄不同，返回比较结果
    } else {
        return p1.getName().compareTo(p2.getName()); // 年龄相同则按名字排序
    }
});

示例代码

以下是一个完整的示例，包括自定义 Comparator 和使用 Lambda 表达式进行排序：

Java
import java.util.Arrays;
import java.util.Comparator;

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
   }

    public int getAge() {
        return age;
    }
}

public class Main {
    public static void main(String[] args) {
        Person[] people = {
            new Person("Alice", 30),
            new Person("Bob", 25),
            new Person("Charlie", 35),
            new Person("David", 25)
        };

        // 按年龄排序
        Arrays.sort(people, Comparator.comparingInt(Person::getAge)
            .thenComparing(Person::getName)); // 若年龄相同则按名字排序

        // 打印排序后的结果
        for (Person p : people) {
            System.out.println(p.getName() + ": " + p.getAge());
        }
    }
}

注意事项

在 compare 方法中，确保传入的对象不为 null，以避免抛出 NullPointerException。
在比较时，如果返回值不符合预期，可能会导致排序错误，因此需要仔细测试自定义的比较器。

3. 排序优化

排序算法在处理不同规模数据时表现各异。以下是一些常见的排序算法及其适用场景，供大家初步了解：

选择排序：适用于小规模数据集，时间复杂度为 (O(n^2))。
它的特点是每次选择未排序部分中的最小值，然后将其与当前元素交换。虽然简单易懂，但性能较差，不适合大数据集。
插入排序：适合于几乎已排序的数据集，时间复杂度也是 (O(n^2))。
插入排序的优势是当数据几乎有序时，它的效率会比选择排序好得多。
快速排序：性能较好的通用排序算法，时间复杂度为 (O(n log n))。
它通过选择一个基准元素（pivot），将数组划分为两部分，并递归地对这两部分进行排序。适合大规模数据集。
归并排序：与快速排序一样，时间复杂度为 (O(n log n))，但它是稳定的排序算法。
归并排序将数组不断拆分，然后合并排序好的子数组。虽然它的性能稳定，但需要额外的内存来存储拆分的数组。
冒泡排序：是一种简单但性能较差的排序算法，时间复杂度为 (O(n^2))。
它的基本思想是通过不断比较相邻的元素并交换它们，将较大的元素“冒泡”到数组的末尾。适用于非常小规模的数据集。
堆排序：基于二叉堆结构的排序算法，时间复杂度为 (O(n log n))。
堆排序通过建立一个最大堆或最小堆来进行排序。虽然堆排序的时间复杂度和快速排序相同，但它不需要额外的内存空间（不像归并排序）。
计数排序：时间复杂度为 (O(n+k))，适用于数据范围较小的场景。
它通过统计每个元素出现的次数来排序，适用于整数排序且数据范围不大的情况。计数排序的性能在数据范围较小时非常优异，但当数据范围很大时，空间消耗会过高。
桶排序：时间复杂度为 (O(n+k))，适合均匀分布的数据集。
它将元素分布到多个桶中，分别对每个桶进行排序，然后再合并所有桶中的元素。对于分布均匀的数据，桶排序的性能非常好，但如果数据分布不均，性能可能会退化。
基数排序：一种非比较排序算法，时间复杂度为 (O(n * k))，适用于处理位数固定的数据。
它通过按位（或数字）进行多次排序来完成整体排序，适用于对整数或字符串进行排序。基数排序的性能在处理大规模、固定位数的数字时较好。

2.1 排序算法例题讲解

2.1.1 LC215：找出数组中的第 `K` 大元素

题目描述：

给定一个未排序的数组，找出其中第 K 大的元素。

解题思路：

可以先对数组进行降序排序，然后直接返回排好序后的数组中的第 K 个元素。

代码实现：

Java
import java.util.Arrays;
import java.util.Comparator;

class Solution {

    // 自定义比较器，进行降序排序
    public int findKthLargest(int[] nums, int k) {
        // 将 int[] 数组转换为 Integer[]，因为 Arrays.sort 不支持原生类型的自定义 Comparator
        Integer[] numsArray = Arrays.stream(nums).boxed().toArray(Integer[]::new);

        // 使用自定义的 Comparator 进行降序排序
        Arrays.sort(numsArray, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return b - a;  // 降序排序
            }
        });

        // 返回排序后的第 K 大元素
        return numsArray[k - 1];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println("The " + k + "th largest element is " + sol.findKthLargest(nums, k));
    }
}

说明：

转换数组类型：Java 中，Arrays.sort() 不支持对原生类型（如 int[]）的自定义比较器。因此，需要将 int[] 转换为 Integer[]，这可以通过 Arrays.stream(nums).boxed().toArray(Integer[]::new) 实现。
自定义排序规则：通过 Comparator<Integer> 接口实现降序排序，比较时 b - a 会将数组元素从大到小排序。
返回第 K 大元素：排序完成后，返回数组中第 K 个元素（数组索引为 k - 1）。

2.2 排序算法举一反三

2.2.1 LC56：合并区间

题目描述

给定若干个闭合区间 [x1, y1], [x2, y2], ...，请将所有重叠的区间合并。例如，区间 [1, 3] 和 [2, 6] 可以合并为 [1, 6]。

解题思路

排序：首先，按照区间的起始值对所有区间进行排序。
遍历：然后遍历每个区间，若当前区间与前一个区间重叠，则合并它们；否则将当前区间直接加入结果列表。

代码实现

Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[][] merge(int[][] intervals) {
        // 如果输入为空，直接返回
        if (intervals.length == 0) return new int[0][0];

        // 按照区间的起始值进行排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();

        // 遍历每一个区间
        for (int[] interval : intervals) {
            // 如果 merged 为空或者当前区间与上一个区间不重叠，直接加入
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                // 如果重叠，更新上一个区间的结束位置
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }

        // 将 List<int[]> 转换为 int[][] 返回
        return merged.toArray(new int[merged.size()][]);
    }
}

讲解

自定义排序：在 Arrays.sort() 中使用 Lambda 表达式来对区间进行排序，确保区间按照起始值升序排列，便于后续的合并操作。
遍历区间：使用增强的 for 循环遍历每个区间。通过比较每个区间的起始值与已合并区间的结束值来判断它们是否重叠：
- 如果没有重叠，则将当前区间直接加入 merged 列表。
- 如果重叠，则更新已合并区间的结束值，确保它可以涵盖当前区间。
结果转换：由于 merged 是一个 List<int[]>，最后使用 toArray() 方法将其转换为 int[][] 类型以返回结果。

2.2.2 LC252：会议室

题目描述

给定一系列会议时间区间，判断是否能让所有会议无冲突地安排在一间会议室中。

解题思路

排序：首先将所有的会议按照开始时间进行排序。
遍历检查：遍历每个会议，检查是否有重叠区间。

代码实现

Java
import java.util.Arrays;

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        // 如果没有会议，直接返回 true
        if (intervals.length == 0) return true;

        // 按照会议的开始时间进行排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // 检查会议是否重叠
        for (int i = 1; i < intervals.length; i++) {
            // 如果当前会议的开始时间小于上一个会议的结束时间，则有重叠
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }

        return true;  // 如果没有重叠，返回 true
    }
}

讲解

排序：使用 Arrays.sort() 方法将会议区间按照开始时间进行排序。Lambda 表达式 (a, b) -> Integer.compare(a[0], b[0]) 用于指定排序的规则。
检查重叠：遍历排序后的会议区间，从第二个会议开始，检查其开始时间是否小于上一个会议的结束时间。如果发现重叠，立即返回 false；如果遍历完所有会议都没有重叠，则返回 true。

2.2.3 LC347：前 K 个高频元素

题目描述：

给定一个非空的整数数组，返回其中出现频率最高的前 K 个元素。

解题思路：

使用哈希表统计每个元素的出现次数。
将哈希表中的元素放入一个数组中，按出现次数从高到低排序。
返回排序后前 K 个元素。

Java
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Map;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 使用哈希表统计每个元素的出现次数
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // 将哈希表中的元素转换为列表
        List<Map.Entry<Integer, Integer>> frequencyList = new ArrayList<>(frequencyMap.entrySet());

        // 使用默认的排序函数按频率降序排列
        frequencyList.sort((a, b) -> b.getValue() - a.getValue());

        // 取出前 K 个频率最高的元素
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = frequencyList.get(i).getKey();
        }

        return result;
    }
}

3. 贪心算法

贪心算法是一种解决问题的策略，其核心思想是：在解决问题的每一步中，总是选择当前看起来最优的选择，通过一系列这样的局部最优选择，最终希望获得全局最优解。

需要注意的是，贪心算法并不总是能得到全局最优解。它只有在某些特定问题中有效，特别是当问题满足贪心选择性质时。

贪心算法的特点

局部最优选择：
贪心算法在每一步中只做出当前看起来最优的选择，而不关心之后可能发生的情况。它不会考虑这次选择是否会影响后续决策，只看当下哪个选项是最有利的。例如，在分数背包问题中，贪心策略是每次优先选择单位重量价值最高的物品，因为它在当前的选择中带来的收益最大。
- 优点：通过每一步的最优选择，可以快速找到一个可行解。贪心算法的规则简单、直观，易于实现，通常可以通过一次扫描或排序解决问题，时间复杂度较低。例如在分数背包问题中，贪心算法只需要按单位价值排序，时间复杂度为 (O(n log n))。
- 缺点：局部最优解不一定能保证全局最优，因为在一些问题中，最佳的整体方案依赖于多步决策的综合效果，而不是单纯的每一步最优。贪心算法无法通过局部最优解找到全局最优解，尤其在复杂问题（如 0-1 背包问题）中，它可能会陷入次优解。
- 不可回溯：
  贪心算法的一个重要特点是决策不可回头修改。一旦做出某个选择，算法就不会再考虑改变它，即使后续发现这个选择可能不是最优的。因为贪心算法依赖的是当前最优选择的策略，所以它不会为未来的选择留下回旋余地。
- 优点：由于不需要回溯，贪心算法执行速度非常快，时间复杂度通常比需要回溯的算法（如动态规划、回溯法等）更低。贪心算法的高效性体现在其快速、直接的解决思路上，适用于处理大规模问题时的高效求解。
- 缺点：由于贪心算法不具备回溯能力，它只能在符合贪心选择性质的问题中有效。如果问题不满足这种性质，算法可能会在后续步骤中陷入次优解或死胡同，无法达到全局最优解。
具体步骤

贪心算法通常遵循以下基本步骤：

明确贪心策略：确定每一步的局部最优解选择策略。
排序：如果问题涉及多个选择，通常需要对其进行排序（如按结束时间、单位价值等）。
逐步选择：根据贪心策略，按照排序结果逐步选择最优项。
检查可行性：每次选择时，确保当前选择满足问题的约束条件（如不冲突、不超出容量等）。
构造解：将所有的选择组合起来，形成问题的最终解。

贪心算法的适用条件

要判断一个问题是否适合使用贪心算法，可以观察以下特征：

贪心选择性质：在每一步中，选择的局部最优解能够保证不会影响后续选择的最优性，即贪心选择在每一步都能保持全局最优。
无后效性：当前的选择不会影响未来的选择。每个选择的结果只依赖当前状态，而不会依赖之前的决策。即一旦做出了某个选择，该选择就不可改变。

如果问题满足以上两点，那么通常可以使用贪心算法求解。

贪心算法 vs 动态规划的判定标准

在区分一个问题是否适合使用贪心算法或动态规划时，最优子结构和子问题重叠是关键的判定标准：

贪心选择的适用条件：
- 局部最优选择性质：贪心算法每一步做出的选择都是局部最优解，且这些局部最优解构成了全局最优解。这种性质一般存在于可以通过逐步选择解决的简单优化问题。
- 无后效性：未来的决策不依赖于之前的选择，因此一旦做出了选择，不需要回溯检查。例如，分数背包问题，每次选择单位价值最高的物品不会影响之后的选择。
动态规划的适用条件：
- 最优子结构：全局最优解依赖于子问题的最优解。如果每个子问题的解都影响到全局最优解，那么这种问题通常需要使用动态规划来解决。背包问题中的0-1 背包问题就属于此类问题，当前物品是否选入背包会影响未来的选择，因此无法简单通过贪心策略得到最优解。
- 子问题重叠：如果问题可以被拆分为多个子问题，且这些子问题之间存在重叠（即某个子问题的解会多次被使用），那么动态规划是更有效的选择。

总结来看，如果问题可以通过单纯的局部最优选择解决，并且未来的选择不依赖于过去的选择，通常可以使用贪心算法；否则需要通过动态规划来解决问题。

简单例子

1. 分数背包问题（贪心算法）

问题描述：你有一个容量为 50 的背包，和一堆物品，每件物品都有重量和价值。你可以将每件物品按任意比例装入背包（例如可以装入物品的一部分），目标是让背包里的物品总价值最大化。

贪心策略：优先选择单位重量价值最高的物品，尽可能多地装入背包。

分析步骤：

明确贪心策略：每次选择单位重量价值最高的物品，尽可能多装入背包。
排序：将所有物品按照单位重量的价值从高到低排序。
逐步选择：按照排序后的顺序，优先选择单位价值最高的物品，直到背包装满。
检查可行性：每次选择物品时，检查背包剩余容量是否足够。如果容量不足，将物品的一部分装入背包。
构造解：将选入背包的物品组合起来，计算总价值，得到问题的解。

2. 0-1 背包问题（动态规划）

问题描述：你有一个容量为 50 的背包和一堆物品，每件物品都有一个确定的重量和价值。你只能选择将某件物品完全放入背包或者不放入，不能只装一部分。目标是选择一些物品放入背包，使得背包中的物品总价值最大化。

动态规划思路：对于每件物品，你需要决定是否放入背包。每次的选择都依赖于背包当前的容量以及之前的选择。因为选择一次物品会影响到后续能装多少东西，所以我们不能使用贪心算法，而需要通过动态规划来考虑所有可能的组合。

用简单的话来理解动态规划的思路：

1.状态：我们用 dp[i][w] 表示前 i 个物品在容量为 w 的背包中所能装的最大总价值。换句话说，dp[i][w] 是一个中间结果，告诉我们如果只考虑前 i 个物品，并且背包容量为 w，我们能装的最高价值是多少。

2.状态转移方程：这个就是动态规划中的“规则”，用来指导我们如何根据前面的计算结果推导出当前的最优解。

对于每件物品 i，你有两种选择：

不选这件物品：那么最大价值就是 dp[i-1][w]，即背包容量保持不变，前面 i-1 个物品的最优解。
选这件物品：如果选择物品 i，则当前的背包容量减少 weight[i]，而我们还获得了 value[i] 这个物品的价值。所以最大价值变成了 dp[i-1][w - weight[i]] + value[i]。

两者取较大值：

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

3.理解这段公式：

如果你不选物品 i，那么你只能依赖前面 i-1 个物品在容量为 w 时的最优解，即 dp[i-1][w]。
如果你选了物品 i，那你需要腾出足够的空间来放它，也就是说背包容量会减少 weight[i]，然后你能获得这件物品的价值 value[i]，再加上前 i-1 个物品在减少了的容量 w - weight[i] 时的最优解，即 dp[i-1][w - weight[i]]。

4.如何求解：我们从空背包开始，逐步增加物品和容量，每次用上面这个公式去更新当前背包容量的最优解。通过这个递推过程，最后就能得到整个背包的最大价值。

举个简单例子：

假设我们有一个背包容量为 5，物品如下：

物品 1：重量 2，价值 3
物品 2：重量 3，价值 4
物品 3：重量 4，价值 5

动态规划表的构建过程：

i\w	2	3	4	5
0	0	0	0	0
1	3	3	3	3
2	3	4	4	7
3	3	4	5	7

当 i = 1（只考虑物品1）：物品1的重量为2，所以当背包容量小于2时，无法放入，价值为0；当容量等于2或大于2时，放入物品1，价值为3。
当 i = 2（考虑前两个物品）：在容量为3时，放入物品2比物品1好，价值为4；当容量为5时，放入物品1和物品2，价值为7。
当 i = 3（考虑三个物品）：物品3太重，不能放入背包，之前的最优值保持不变。

最终，我们得到的最大价值为7。

3. 活动选择问题（贪心算法）

问题：你有一系列活动，每个活动都有开始时间和结束时间。你需要选择尽可能多的活动，并且这些活动不能重叠。

贪心策略：每次选择结束时间最早且不与其他活动冲突的活动。

步骤： 1. 明确贪心策略：每次选择结束时间最早的活动，以留出更多时间给其他活动。 2. 排序：将活动按结束时间从早到晚排序。 3. 逐步选择：从第一个活动开始，依次选择结束时间最早且与之前活动不冲突的活动。 4. 检查可行性：每次选择活动时，检查该活动是否与已经选择的活动冲突。 5. 构造解：将每次选择的活动加入最终解，直到没有活动可以再选。

贪心算法的局限性

贪心算法并不总是能找到最优解。比如：

1. 0-1 背包问题

在这个问题中，你必须选择完整的物品（要么全选，要么不选），而不能选择物品的一部分。如果你使用贪心算法来选择单位价值最高的物品，很可能会因为重量限制而无法选择最优组合。

2. 最短路径问题

在某些图上，贪心策略（总是选择距离最近的节点）并不总能找到最短路径。

总结：

贪心算法是一种简单而高效的策略，适合用在那些可以通过局部最优解得到全局最优解的问题上。它的关键在于每一步都做出最好的局部选择，希望最终得到最优解。虽然并不是所有问题都适合用贪心算法，但在合适的情况下，它能快速找到解。

3.1 贪心算法例题讲解

3.1.1 LC455: 分发饼干

题目描述

给定两个数组，g 表示孩子的需求大小，s 表示饼干的大小。请你尽可能地用饼干满足孩子的需求，每个孩子最多只能获得一块饼干。如果一个孩子的需求得到满足，那么这个孩子就可以快乐地吃到饼干。请你返回能够使多少个孩子满足。

代码实现

Java
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        // 将孩子的需求和饼干的大小排序
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0; // 指向孩子的指针
        int j = 0; // 指向饼干的指针

        // 遍历孩子和饼干数组
        while (i < g.length && j < s.length) {
            // 如果当前饼干能满足当前孩子
            if (s[j] >= g[i]) {
                i++; // 满足了孩子 i，处理下一个孩子
            }
            j++; // 尝试下一个饼干
        }

        return i; // 返回满足的孩子数量
    }
}

代码讲解

排序步骤：
- 使用 Arrays.sort() 方法对孩子的需求数组 g 和饼干大小数组 s 进行排序。这样可以确保较小的需求与较小的饼干配对，从而尽量使用最小的饼干满足最小需求的孩子。
匹配过程：
- 使用两个指针 i 和 j，分别指向孩子和饼干数组的开始位置。
- 在 while 循环中，检查当前饼干是否能满足当前孩子的需求。如果 s[j]（当前饼干）大于等于 g[i]（当前孩子的需求），则认为该孩子得到了满足，移动 i 指针，准备处理下一个孩子。
- 不论饼干是否满足孩子，j 指针都会向前移动，尝试下一个饼干。

3.2 贪心算法举一反三

3.2.1 LC 435: 无重叠区间

题目描述

给定一组区间，找到最少需要移除的区间数量，使得剩下的区间互不重叠。

贪心算法步骤： 1. 排序：按照区间的结束时间进行升序排序。排序后，我们可以优先选择结束时间较早的区间，这样能够为后续区间留出更多空间，减少冲突。

选择区间：每次选择结束时间最早且不与前一个选择的区间重叠的区间。如果当前区间的开始时间小于前一个区间的结束时间，说明发生了重叠，我们就需要移除当前区间。否则，我们更新当前区间为新的结束时间，并继续处理下一个区间。

代码实现

Java
import java.util.Arrays;

class Solution {
    // 自定义比较函数，按结束时间排序
    private static class IntervalComparator implements java.util.Comparator<int[]> {
        @Override
        public int compare(int[] a, int[] b) {
            return Integer.compare(a[1], b[1]); // 按照区间的结束时间升序排列
        }
    }

    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;

        // 按区间的结束时间进行排序
        Arrays.sort(intervals, new IntervalComparator());

        int count = 0;
        int end = intervals[0][1]; // 当前选定区间的结束时间

        // 遍历剩余区间
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                count++; // 发生重叠，增加移除的区间数
            } else {
                end = intervals[i][1]; // 更新当前选定区间的结束时间
            }
        }

        return count; // 返回被移除的区间数
    }
}

代码讲解

自定义比较函数：
- 使用 IntervalComparator 类实现 Comparator 接口，按区间的结束时间进行排序。
排序步骤：
- 使用 Arrays.sort() 方法将区间按结束时间升序排序。这样可以确保我们每次选择的区间结束得最早，能为后续的区间留出更多空间，减少重叠的可能性。
遍历选择区间：
- 初始化一个 end 变量，表示当前选定区间的结束时间。遍历剩余的区间，检查每个区间的开始时间是否与当前选定的结束时间发生重叠。如果当前区间的开始时间小于 end，则说明发生了重叠，必须移除该区间。如果没有重叠，则更新 end 为当前区间的结束时间。

3.2.2 LC 605: 种花问题

题目描述

给定一个表示花坛的整数数组 flowerbed，其中 flowerbed[i] = 0 表示该位置是空的，flowerbed[i] = 1 表示该位置已经种了花。花坛中花不能种在相邻的地块上，问是否能够在不违反规则的情况下再种下 n 朵花。

贪心算法步骤： 1. 遍历花坛：从左到右依次检查每个位置。如果当前位置是空的 0，并且它的前一个位置和后一个位置也是空的（如果存在），那么可以在这个位置种花。

计数并跳过相邻位置：每次成功种花后，增加计数，并跳过下一个位置，因为相邻位置不能种花。

代码实现

Java
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;  // 记录可以种花的数量

        // 遍历整个花坛
        for (int i = 0; i < flowerbed.length; i++) {
            // 判断当前位置是否可以种花（检查前后位置，注意边界条件）
            if (flowerbed[i] == 0 && 
                (i == 0 || flowerbed[i - 1] == 0) && 
                (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {

                flowerbed[i] = 1;  // 种花
                count++;  // 计数增加
                i++;  // 跳过下一个位置，避免相邻种花
            }
            if (count >= n) return true;  // 如果种够 n 朵花，返回 true
        }
        return count >= n;  // 遍历结束，检查是否种够 n 朵花
    }
}

代码讲解

遍历判断能否种花：
- 遍历整个 flowerbed 数组，检查每个位置是否可以种花。当前的位置必须满足三个条件才能种花：当前位置为 0，前一个位置（如果存在）为 0，后一个位置（如果存在）也为 0。在检查边界时（第一个和最后一个位置），可以用条件语句避免访问不存在的前后位置。
种花后跳过相邻位置：
- 每次成功种花后，更新 flowerbed 数组，将当前的位置设置为 1，并增加 count 计数。同时，跳过下一个位置（i++），因为相邻的位置不能再种花。
提前终止：
- 如果在遍历过程中已经种够了 n 朵花，则可以提前返回 true。如果遍历结束后还没有种够，则返回 false。

3.2.3 LC 1029: 两地调度

题目描述：

有 2N 个人，每个人都需要飞往 A 市或 B 市。给定一个 costs 数组，其中 costs[i] = [aCost, bCost] 表示第 i 个人飞往 A 市的费用和飞往 B 市的费用。现在需要把这些人分配到两个城市，使得 N 个人飞往 A 市，N 个人飞往 B 市，要求总费用最小。

贪心算法步骤： 1. 计算成本差异：我们计算每个人去 A 市和 B 市的费用差，即 aCost - bCost。我们希望优先让那些去 B 市更便宜的人去 B 市，而让去 A 市更便宜的人去 A 市。

排序选择：根据去 A 市和 B 市的费用差异排序。差异越大的人，意味着去 A 市或 B 市对成本影响越大，因此我们优先考虑这些人。
分配城市：前 N 个人安排到 A 市，后 N 个人安排到 B 市，最终得到最小的总费用。

代码实现

Java
import java.util.Arrays;

class Solution {
    public int twoCitySchedCost(int[][] costs) {
        // 自定义比较函数，按去 A 市和 B 市的费用差进行排序
        Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));

        int totalCost = 0;
        int n = costs.length / 2;

        // 前 N 个人去 A 市，后 N 个人去 B 市
        for (int i = 0; i < n; i++) {
            totalCost += costs[i][0];  // 去 A 市的费用
        }
        for (int i = n; i < 2 * n; i++) {
            totalCost += costs[i][1];  // 去 B 市的费用
        }

        return totalCost;
    }
}

代码讲解

计算成本差异：
- 每个人有去 A 市和 B 市的两种选择，我们可以通过 aCost - bCost 来衡量每个人去 A 市的额外成本。如果 aCost < bCost，说明让这个人去 A 市更划算，反之则去 B 市更划算。
排序步骤：
- 使用 Java 的 Arrays.sort() 方法对 costs 数组进行排序，排序依据为 aCost - bCost。这确保了那些去 A 市更便宜的人会被优先安排去 A 市，而去 B 市更便宜的人会被安排去 B 市。
分配城市：
- 排序后，前一半的人去 A 市，后一半的人去 B 市。这样可以确保在总费用最小的情况下，平衡去两座城市的人数。
返回结果：
- 最终返回总的费用，即前 N 个人的 A 市费用和后 N 个人的 B 市费用之和。

4. 课后练习

排序问题

题目编号	题目名称	简介
LC1288	删除被覆盖的区间	给定一组区间，找出其中未被覆盖的区间，移除被覆盖的区间。
LC1024	视频拼接	给定一组区间，判断是否能够通过拼接区间覆盖整个视频长度。
LC763	划分字母区间	给定一个字符串，将其划分为尽可能多的不重叠的区间，使得每个字母最多出现在一个区间中。
LC57	插入区间	给定一组非重叠的区间和一个新的区间，将新区间插入并合并所有可能的重叠区间。
LC179	最大数	给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

贪心算法问题

题目编号	题目名称	简介
LC121	买卖股票的最佳时机	给定股票价格，找到在最佳时机买入和卖出以获得最大利润。
LC122	买卖股票的最佳时机 II	允许多次买卖，找到在最佳时机买入和卖出以获得最大利润。
LC55	跳跃游戏	给定一个数组，判断是否能跳到数组的最后一个位置。
LC45	跳跃游戏 II	给定一个数组，找到跳到数组最后一个位置的最少跳跃次数。
LC409	最长回文串	给定一个字符串，找到其中能组成的最长回文串的长度。

Lesson 13. 时间复杂度，排序和贪心算法

目录

1. 时间复杂度简介

常见的时间复杂度

为什么是 O(n log n)?

时间复杂度总结

具体实例

步骤分析

随堂练习

判断以下代码的时间复杂度

解答

2. 排序算法与应用

适用场景

常用技巧

1. 内置排序函数

2. 自定义排序

自定义 Comparator

方法一：实现 Comparator 接口

方法二：使用 Lambda 表达式（Java 8 及以上）

多重排序

示例代码

注意事项

3. 排序优化

2.1 排序算法例题讲解

2.1.1 LC215：找出数组中的第 K 大元素

题目描述：

解题思路：

代码实现：

说明：

2.2 排序算法举一反三

2.2.1 LC56：合并区间

题目描述

解题思路

代码实现

讲解

2.2.2 LC252：会议室

题目描述

解题思路

代码实现

讲解

2.2.3 LC347：前 K 个高频元素

题目描述：

解题思路：

3. 贪心算法

贪心算法的特点

具体步骤

贪心算法的适用条件

贪心算法 vs 动态规划的判定标准

简单例子

1. 分数背包问题（贪心算法）

分析步骤：

2. 0-1 背包问题（动态规划）

用简单的话来理解动态规划的思路：

举个简单例子：

3. 活动选择问题（贪心算法）

贪心算法的局限性

1. 0-1 背包问题

2. 最短路径问题

总结：

3.1 贪心算法例题讲解

3.1.1 LC455: 分发饼干

题目描述

代码实现

代码讲解

3.2 贪心算法举一反三

3.2.1 LC 435: 无重叠区间

题目描述

代码实现

代码讲解

3.2.2 LC 605: 种花问题

题目描述

代码实现

代码讲解

3.2.3 LC 1029: 两地调度

题目描述：

代码实现

代码讲解

4. 课后练习

排序问题

贪心算法问题

为什么是 `O(n log n)`?

方法一：实现 `Comparator` 接口

2.1.1 LC215：找出数组中的第 `K` 大元素