我的笔记

Appearance

🍕 递归 ​

递归案例 - 求数组最大值 ​

java
public static int process(int[] arr, int L, int R) {
    if (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 可能溢出, 故改写成 L + (R-L) / 2 。 除以 2 可以使用位运算 >>1 实现。

举个🌰: 数组长度 5, 使用递归求最大值的过程如下:

                [0, 4]                      0 + (4-0)>>2 = 2
              /        \
        [0, 2]          [3, 4]              0+(2-0)>>2 = 1      ;   3+(4-3)>>2 = 3
       /     \         /      \
    [0, 1]   [2]     [3]      [4]           0+(1-0)>>2 = 0
    /    \
  [0]    [1]
  1. push; 计算 [0,4] 的最大值, 二分为 [0,2] 和 [3,4],等待 [0,2] 和 [3,4] 各自的最大值
  2. push; 计算 [0,2] 的最大值, 二分为 [0,1] 和 [2],等待 [0,1] 和 [2] 各自的最大值
  3. push; 计算 [0,1] 的最大值, 二分为 [0] 和 [1],等待 [0] 和 [1] 各自的最大值
  4. push; 计算 [0] 的最大值, 直接返回 [0] 的值
  5. pop; 得到 [0] 的最最大值
  6. push; 计算 [1] 的最大值, 直接返回 [1] 的值
  7. pop; 得到 [1] 的最大值
  8. pop; 比较 [0] 和 [1] 得出 [0,1] 的最大值
  9. push; 计算 [2] 的最大值, 直接返回 [2] 的值
  10. pop; 得到 [2] 的最大值
  11. pop; 比较 [0,1] 和 [2] 得出 [0,2] 的最大值
  12. push; 计算 [3,4] 的最大值, 二分为 [3] 和 [4],等待 [3] 和 [4] 的各自最大值
  13. push; 计算 [3] 的最大值, 直接返回 [3] 的值
  14. pop; 得到 [3] 的最大值
  15. push; 计算 [4] 的最大值, 直接返回 [4] 的值
  16. pop; 得到 [4] 的最大值
  17. pop; 比较 [3] 和 [4] 得出 [3,4] 的最大值
  18. pop; 比较 [0,2] 和 [3,4] 得出 [0,4] 的最大值
  19. 结束

                           ⇓[0]      ⇑      ⇓[1]      ⇑
                  ⇓[0,1]   [0,1]   [0,1]    [0,1]   [0,1]     ⇑     ⇓[2]      ⇑                     ⇓[3]      ⇑     ⇓[4]      ⇑
          ⇓[0,2]   [0,2]   [0,2]   [0,2]    [0,2]   [0,2]   [0,2]   [0,2]   [0,2]     ⇑    ⇓[3,4]   [3,4]   [3,4]   [3,4]   [3,4]     ⇑
  ⇓[0,4]   [0,4]   [0,4]   [0,4]   [0,4]    [0,4]   [0,4]   [0,4]   [0,4]   [0,4]   [0,4]   [0,4]   [0,4]   [0,4]   [0,4]   [0,4]   [0,4]    ⇑     END
     1       2       3       4       5        6       7       8       9       10      11      12      13      14      15      16      17     18     19

求递归时间复杂度 - master 公式 ​

满足以下递归关系的递归, 可以使用 master 公式计算时间复杂度

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

其中:

  • T(N) 表示问题规模为 N 时的时间复杂度
  • a 表示子问题的数量
  • N/b 表示每个子问题的规模
  • O(N^d) 表示除去子问题外的其他操作所需的复杂度

计算方法如下(证明略):

  • log_b(a) 表示以 b 为底 a 的对数
  • 如果 log_b(a) > d, 则时间复杂度为 O(N^log_b(a))
  • 如果 log_b(a) = d, 则时间复杂度为 O(N^d * logN)
  • 如果 log_b(a) < d, 则时间复杂度为 O(N^d)

以前面的递归求数组最大值为例:

  • 数组 arr 的长度就是问题规模 N
  • 子问题就是求解 leftMax 和 rightMax, 共有两个子问题, 所以 a = 2
  • 因为子问题的问题规模是原本规模的 1/2, 所以子问题规模为 n/2, 即 b = 2
  • 除去子问题外, 剩下的就是一个 if 判断, 一个 mid 值的计算和 Math.max() 的计算, 所以 O(N^d) 的时间复杂度是 O(1), 即 d = 0
  • 由于 log_b(a) = 1 > 0, 所以时间复杂度为 O(N^log_b(a)) = O(N)

注意⚠️, 只有需要满足上面给定的递归关系的递归, 才能使用 master 公式求解复杂度。

还是以刚才的代码举例, 假设每次递归时, leftMax 选取的是 左侧 1/3 的内容, rightMax 选取的是右侧 2/3 的内容, 这种情况下, 一个子问题规模是 n/3 另一个子问题规模是 2n/3 这就不满足前面的递归关系, 所以无法使用 master 求解复杂度。

还是以刚才的代码举例, 假设每次递归时, 有三个子问题, 每个子问题规模为 1/3, 即将数据划分为三份, 分别求取三份各自的最大值, 再比较三个最大值谁大。 这种情况下, 还是满足前面的递归关系的, 因为子问题规模相同。 只不过此时的 a = 3, b = 3。

🍕 归并排序 ​

基本思路: 将数据分为两份, 然后依次对其中两份进行排序, 排序后再将这两份合并起来。 这是一个递归的过程。

老师代码:

java
public static void mergeSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    process(arr, 0, arr.length - 1);
}

public static void process(int[] arr, int L, int R) {
    if (L == R) {
        return;
    }
    int mid = L + ((R - L) >>1);
    process(arr, L, mid);   // 左侧排好序
    process(arr, mid+1, R); // 右侧排好序
    merge(arr, L, mid, R);  // 将两侧合并
}

public static void merge(int[] arr, int L, int M, int R) {
    int[] help = new int[R - L + 1];    // 创建一块备份空间, 用于存放合并后的数组
    int i = 0;      // 用于 help 的下标
    int p1 = L;     // 用于左侧的下标
    int p2 = M + 1; // 用于右侧的下标

    // 将左右两侧的内容存放到 help 数组中
    while (p1 <= M && p2 <= R) {
        help[i++] = arr[p1] <= arr[p2]? arr[p1++] : arr[p2++];
    }
    // 前面结束后, 左右两侧一定右一个时间到达边界, 一个未到达边界, 所以下面两个 while 只会执行其中一个
    while (p1 <= M) { // 左侧未到达边界, 则直接将左侧剩下的数放到 help 中
        help[i++] = arr[p1++];
    }
    while (p2 <= M) { // 右侧未到达边界, 则直接将右侧剩下的数放到 help 中
        help[i++] = arr[p2++];
    }
    // 将排好序后的 help 数组复制到原数组中
    for (i = 0; i < help.length; i++) {
        arr[L+i] = help[i];
    }
}

利用前面的 master 公式求解时间复杂度。

其中的 process 函数是一个递归函数, 它有两个子问题, 子问题规模是 N/2, 除去子问题外的时间复杂为主要由 merge 函数占用。 merge 函数不是递归函数, 求解时间复杂度比较简单, 时间复杂度很容易得出是 O(N)。 所以列出递归关系为 2 * log_2(N) + O(N), 其中 a = 2, b = 2, d = 1, 满足 log_b(a) = d, 故时间复杂度为 O(N^d * logN) = O(N*logN)

🍕 归并排序比 选择,冒泡,插入排序 好在哪里 ​

前面的三种排序(选择,冒泡和插入)的时间复杂度都是 O(N^2), 而归并排序的复杂度是 O(N*logN)。 即归并排序将其中一个 N 优化成了 logN。

前面三类排序差就差在浪费了比较的机会, 每次比较的信息都直接被丢弃了, 比如选择排序, 第一次比较了 N-1 次, 结果就只排序好一个数, 然后又比较 N-2 次, 又只排序好一个数。 而归并排序保存了比较的信息, 归并排序在, 只在 merge 合并的过程中进行了比较, 并且这个比较的信息保留下来了, 具体体现在每次比较(merge)后的数组都是有序的。

主要注意的是, 前面给出的归并排序的空间复杂度是 O(N), 因为在 merge 的过程中定义了一个 help 临时数组用于存储排序后的内容。

🍕 归并排序变体 - 小和问题 ​

在一个数组中, 将每一个数左边中比当前数小的所有数字累加起来，叫做这个数组的小和。 注意⚠️, 小和是只看数的左边, 而不是两边

举个例子说明: 有这么一个数组 [1,3,4,2,5],

  • 1 左边没有比 1 小的数;
  • 3 左边比 3 小的数有 1, 此时 小和 += 1;
  • 4 左边比 4 小的数有 1,3, 此时 小和 += (1+3)
  • 2 左边比 2 小的数有 1, 此时 小和 += 1;
  • 5 坐标比 5 小的数有 1,3,4,2, 此时 小和 += (1+3+4+2)
  • 故这个数组的小和为 16

暴力解法: 从左到右依次遍历每个数; 对于每个数, 遍历当前数的左侧, 将所有比当前数小的数相加起来求出小和。 这种方式的时间复杂度是 O(N^2)

正常流程是在左侧求比当前数小的数, 然后将他们加起来求小和; 但我们可以反过来: 遍历右侧查看有多少个数比当前数大, 然后将这个数量和当前数相乘得出小和。

这种方式的暴力解法为: 从左到右依次遍历每个数; 对于每个数, 遍历当前数的右侧, 统计有多少个数比当前数大, 然后将这个数量与当前数相乘得到小和。 时间复杂度依然是 O(N^2)

归并排序解决小和问题 - 过程描述 ​

首先, 会先对数组进行递归分组, 如下所示:


                    [1,3,4,2,5]
                 /             \
            [1,3,4]            [2,5]
            /     \           /     \
        [1,3]     [4]        [2]   [5]
        /   \
     [1]    [3]

然后自底向上依次排序合并, 在这个过程中求小和。

先求 小和[1] 和 小和[3], 它们的值都是 0。再求合并后的 小和[1,3] 的值:

定义左右两个指针, 分别指向 左侧[1] 和 右侧[3]。 判断左侧指针所指的数是否小于右侧指针所指的数, 如果左侧小于右侧, 则直接通过右侧指针和右侧数组的长度, 求出右侧右多少个数比左侧大。 （这里就是关键, 因为不需要遍历右侧数组, 而是直接一步到位求出右侧比当前数大的数量）

如果右侧先到达边界, 说明左侧中剩余的数都大于右侧的数, 此时他们的小和都是 0 。 如果左侧先到达边界, 此时已经将左侧中所有数的小和已经求取完毕。

求 小和[1,3] 如下所示:

        [1,3]      return 0 + 0 + 1*1 = 1
        /   \
     [1]    [3]    return 0    ;    return 0

求 小和[4], 值为 0。 再求合并后的 小和[1,3,4] 的值, 具体步骤和上面一样, 小和[1,3,4] 的值如下所示:

           [1,3,4]      return  1 + 0 + (1*1 + 3*1) = 5
           /     \
       [1,3]     [4]    return  1    ;     return 0
       /   \
    [1]    [3]

接下来 [1,3,4] 需要和右侧 [2,5] 合并, 求 小和[1,3,4,2,5] 的值, 所以需要先求 小和[2,5] 的值

小和[2] 和 小和[5] 的值都是 0。 再求 小和[2,5] 的值, 如下所示:

     [2,5]      return 0 + 0 + (2*1) = 2
    /     \
   [2]   [5]    return 0    ;    return 0

现在可以求 [1,3,4] 和 [2,5] 合并后的 小和[1,3,4,2,5] 的值了, 如下所示:

          [1,2,3,4,5]       return 5 + 2 + (1*2 + 3*1 + 4*1) = 16
         /          \
    [1,3,4]         [2,5]   return 5   ;   return 2

如何保证小和不重不漏? ​

归并排序求小和问题能够保证求解出的小和不会重复也不会遗漏, 具体看下面案例说明:

假设数组为 [a,b,c,d,e,f], 它的划分如下:

            [a,b,c,d,e,f]
            /           \
        [a,b,c]        [d,e,f]
        /     \         /     \
    [a,b]     [c]    [d,e]    [f]
    /   \            /   \
  [a]   [b]        [d]  [e]

对于数组 [a,b,c,d,e,f], 我们求小和的目的就是找出每一个数字的 右边 拥有的大于该数的数量, 然后将这个数量与该数相乘得到一个结果(result), 然后将所有数的结果相加, 就是这个数组的小和。

我们使用归并排序计算小和的过程中, 每次求取的数的范围是从左到右慢慢变大的, 并且这个范围不会重叠, 也不会漏选。

比如, 对于数字 a, 先求他在右侧范围 [b] 下的小和, 然后再求它在右侧范围 [c] 下的小和, 最后求他在右侧范围 [d,e,f] 下的小和。 可以看出, 它的所有右侧范围不会有重叠的地方, 同时这些范围也包含了所有的右侧数。

小和问题老师代码: ​

java

public static void smallSum(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    return process(arr, 0, arr.length - 1);
}

// 处理 [L, ..., R] 过程中, 既要排好序, 也要求小和
public static void process(int[] arr, int L, int R) {
    if (L == R) {
        return 0;
    }
    int mid = L + ((R - L) >>1);
    // 注意左右是相对而言的, 在左侧里面同样也有左右之分, 在右侧中同样也有左右之分
    return process(arr, L, mid)     // 左侧排好序, 并且求左侧的小和
        +  process(arr, mid+1, R)   // 右侧排好序, 并且求右侧的小和
        +  merge(arr, L, mid, R);   // 两侧合并排好序后, 求小和
}

public static void 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) {
        // 排序前, 先求小和
        res += arr[p1] < arr[p2]
            ? (R - p2 + 1) * arr[p1] // 小和 = 左组大于当前数的数量 * 右组当前数; arr[p1] 是右组的当前数
            : 0 ;
        // 注意这里, 左右两组相等时, 有限拷贝左组, 即先移动左组的指针
        help[i++] = arr[p1] < arr[p2]? arr[p1++] : arr[p2++];
    }
    // 前面 while 已经求出右组中的所有数在当前 arr 下能产生的小和总数了, 后面内容只是用于排序
    while (p1 <= M) {
        help[i++] = arr[p1++];
    }
    while (p2 <= M) {
        help[i++] = arr[p2++];
    }
    for (i = 0; i < help.length; i++) {
        arr[L+i] = help[i];
    }
    return res
}

注意:

  • 排序步骤不能少, 因为排序后, 才能够直接计算出右组中有几个数比左组当前数的大, 没有排序的话, 就需要遍历, 这个时候复杂度就不是 O(1) 了
  • 当下标指向的左右两组的数值相等时, 一定是先将右组的内容拷贝到 help 数组中, 即移动右组的下标, 左组下标不动。

🍕 快排前菜 - 荷兰国旗问题 ​

问题 1 - 两项划分(Two-Way Partitioning) ​

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

基本思路:

  • 利用一个变量 l 来指定 "≤ num 区域" 的边界, l 初始值为 -1, 代表 "≤ num 区域" 为空。
  • 遍历数组, 当数值 ≤ num 时, 将该数和 [l+1] 位置的数交换, 然后 l++, 表示 "≤ num 区域" 变大。
  • 当数值 > num 时, 不做处理。 但指针还是会继续指向下一个, 即循环会继续。

原理: 创建一个 "≤ num 区域", 遍历数组时, 确保 ≤ num 的数字能够被划入 "≤ num 区域" 内, 而 > num 的数字能够被排除的 "≤ num 区域" 外面

举个🌰: 数组 [3,5,6,7,4,3,8], num 为 5

初始: l = -1
            ━━┓
            ≤ ┃ 3 5 6 7 4 3 8
            ━━┛ ↑
识别到 3 ≤ 5, 交换当前数, 并且 l++, 指针指向下一个

            ━━┓
          3 ≤ ┃   5 6 7 4 3 8
            ━━┛   ↑
识别到 5 ≤ 5, 交换当前数, 并且 l++, 指针指向下一个

            ━━┓
        3 5 ≤ ┃     6 7 4 3 8
            ━━┛     ↑
识别到 6 > 5, 指针指向下一个

            ━━┓
        3 5 ≤ ┃     6 7 4 3 8
            ━━┛       ↑
识别到 7 > 5, 指针指向下一个

            ━━┓
        3 5 ≤ ┃     6 7 4 3 8
            ━━┛         ↑
识别到 4 ≤ 5, 交换当前数, 并且 l++, 指针指向下一个

            ━━┓
      3 5 4 ≤ ┃       7 6 3 8
            ━━┛           ↑
识别到 3 ≤ 5, 交换当前数, 并且 l++, 指针指向下一个

            ━━┓
    3 5 4 3 ≤ ┃         6 7 8
            ━━┛             ↑
识别到 8 > 5, 指针指向下一个, 发现到达边界, 故退出

问题 2 - 三项划分(Three-Way Partitioning) ​

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

基本思路:

  • 利用一个变量 l 来指定 "< num 区域" 的边界, l 初始值为 -1, 代表 "< num 区域" 为空。
  • 利用一个变量 r 来指定 "> num 区域" 的边界, r 初始值为 数组长度, 同样表示 "> num 区域" 为空。
  • 遍历数组, 当数值 < num 时, 当前数和 [l+1] 位置的数交换, 表示 "< num 区域" 变大, 同时指针指向下一个数
  • 当数值 = num 时, 指针直接指向下一个
  • 当数值 > num 时, 当前数和 [r-1] 位置的数交换, 表示 "> num 区域" 变大, 此时指针不动, 因为还没有处理当前指针位置上出现的新的数值

原理: 和问题 1 差不多, 只不过这里定义了两个区域来保存数, 遍历数组, 将符号条件的数划入对应区域即可

举个🌰: 数组 [3,5,6,7,4,3,8], num 为 5

初始: l = -1
            ━━┓                ┏━━
            < ┃ 3 5 6 7 4 3 8  ┃ >
            ━━┛ ↑              ┗━━
识别到 3 < 5, l++, 然后交换当前数到 [l], 指针指向下一个

            ━━┓                ┏━━
          3 < ┃   5 6 7 4 3 8  ┃ >
            ━━┛   ↑            ┗━━
识别到 5 = 5, 指针指向下一个

            ━━┓                ┏━━
          3 < ┃   5 6 7 4 3 8  ┃ >
            ━━┛     ↑          ┗━━
识别到 6 > 5, r--, 然后交换当前数到 [r], 指针不动

            ━━┓                ┏━━
          3 < ┃   5 8 7 4 3    ┃ > 6
            ━━┛     ↑          ┗━━
识别到 8 > 5, r--, 然后交换当前数到 [r], 指针不动

            ━━┓                ┏━━
          3 < ┃   5 3 7 4      ┃ > 8 6
            ━━┛     ↑          ┗━━
识别到 3 < 5, l++, 然后交换当前数到 [l], 指针指向下一个

            ━━┓                ┏━━
        3 3 < ┃     5 7 4      ┃ > 8 6
            ━━┛       ↑        ┗━━
识别到 7 > 5, r--, 然后交换当前数到 [r], 指针不动

            ━━┓                ┏━━
        3 3 < ┃     5 4        ┃ > 7 8 6
            ━━┛       ↑        ┗━━
识别到 4 < 5, l++, 然后交换当前数到 [l], 指针指向下一个

            ━━┓                ┏━━
      3 3 4 < ┃       5        ┃ > 7 8 6
            ━━┛                ┗━━ ↑
指针进入 "> num 区域", 结束

🍕 快速排序 1.0 版本 ​

基本思路:

  • 取数组最后一个数作为 num, 将前面的所有元素作为 arr,
  • 然后执行前面的荷兰国旗问题一, 将数组划分两部分,
  • 将 num 和分界点位置的值交换, 此时能够保证 num 的位置是正确的
  • 对划分后的两部分, 对他们继续之前上述步骤, 即递归执行, 直到所有值都排好序

原理: 利用前面的荷兰国旗问题, 不断递归, 每次递归都能保证有一个数的位置是正确的。

🍕 快速排序 2.0 版本 ​

2.0 版本和 1.0 版本类似, 区别只在于 1.0 版本执行的是两项划分, 而 2.0 版本执行的是三项划分。 三项划分情况下, 每次递归可能能够将一批相等数据排好序, 所以顺序稍微快点。

快排中, 每次划分的过程, 叫做 partition。 最坏的情况, 每次 partition, 划分值都在两侧, 时间复杂度是 O(N^2)。 最好的情况, 每次 partition, 划分值都在中间, 这种情况下满足 master 算法, 递归关系为 T(N)=2*T(N/2)+O(N), 所以复杂度是 O(N*log(N)

🍕 快速排序 3.0 版本 ​

快排 1.0 和 2.0 两个版本, 时间复杂度都是 O(N^2), 因为每次都是拿最后一个数进行划分, 所以很容易掉入最坏情况。

而快排 3.0 版本, 和前面的区别只在于随机选取一个划分数, 因为是随机选取, 所以在数学上, 各种情况, 包括最好的情况和最坏的情况出现的概率都是相同的。 比如, 可能选取的划分数是在最边边的, 也可能是在 1/5 的位置, 也可能是在 1/3 的位置, 也可能是在 1/2 的位置。 总之, 划分数在每个位置上都是等概率事件, 对所有的情况的概率和复杂度累加, 求数学期望, 得出的复杂度是 O(N*log(N))。 (具体证明过程略)

老师代码:

java
public static void runQuickSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    quickSort(arr, 0, arr.length - 1);
}

public static void quickSort(int[] arr, int L, int R) {
    if (L < R) {
        // 等概率随机取一个数, 将它和最后位置进行交换
        swap(arr, L + (int)(Math.random() * (R - L + 1)), R);
        // 对 L, R 进行划分, 返回的是划分后的边界
        int[] p = partition(arr, L, R);
        // p[0] 是 "< 区"的右边界, p[1] 是 "> 区"的左边界
        quickSort(arr, L, p[0] - 1); // "< 区"
        quickSort(arr, p[1] - 1, R); // "> 区"
    }
}

// 三项划分
public static int[] partition(int[] arr, int L, int R) {
    int less = L - 1; // "< 区" 的右边界; 即  (..., less]
    int more = R; // "> 区" 的左边界; 即 [more, ...); 注意, 最后位置上的值 [R] 是划分数, 不被认为是 "< 区" 的内容
    while (L < more) {
        if (arr[L] < arr[R]) {  // 当前值 < 划分值
            swap(arr, ++less, L++);
        } else if (arr[L] > arr[R]) { // 当前值 > 划分值
            swap(arr, --more, L);
        } else {
            L++;
        }
    }
    // 将划分值放到正确的位置上
    swap(arr, more, R);
    return new int[] {less+1,  more};
}