讨论/技术交流/「春招学习计划」 周常总结 Week8/
「春招学习计划」 周常总结 Week8

「春招学习计划」 周常总结 Week8

简介

大家好,我负责「春招学习计划」第八周(2021.03.8 - 2021.03.15) 的Leetor,这周学习计划主要内容是排序算法。

以下是往期总结链接:

  • Week 1 主要内容:数组、二分查找、并查集。
  • Week 2 主要内容:数组、字符串、KMP 和字典树。
  • Week 3 主要内容:双指针、滑动窗口。
  • Week 4 主要内容:栈、队列。
  • Week 5 主要内容:链表、哈希表。
  • Week 6 主要内容:树、图。
  • Week 7 主要内容:递归、位运算、数学

排序算法

除了Leetbook,推荐看一下oi-wiki 排序简介。下面总结下这周出现的排序算法问题。

对于排序算法,需要先了解几个内容:

  1. 算法的平均复杂度和最坏复杂度。例如归并排序平均和最坏时间复杂度均为O(nlogn)O(n\log n) ,但快速排序最坏复杂度为O(n2)O(n^2)(如数组接近有序情况下)。
  2. 排序算法的稳定性。稳定的排序算法指排序后具有相同值的元素间相对位置关系不会发生变化。

除了面试,推荐熟练使用Python sorted(), list.sort() 和 C++ std::sort() 他们都是最坏时间复杂度O(nlogn)O(n\log n) 的方法。

冒泡排序

思路:相邻元素两两交换将最值移动到数组末端。

  • 平均复杂度 O(n2)O(n^2)
  • 最坏复杂度 O(n2)O(n^2)
  • 稳定

优化思路,均为常数优化

  • 使用变量储存在当前轮冒泡排序中是否进行交换操作。如果位进行交换说明数组已经有序,可提前终止。
  • LeetBook 介绍了鸡尾酒排序
插入排序

思路:数组被划分为有序和无序部分,每次从无序部分选择一个数字插入到有序部分。

  • 平均复杂度O(n2)O(n^2)
  • 最坏复杂度O(n2)O(n^2)
  • 稳定

注意即使插入过程中使用二分法查找插入点,也不能将复杂度优化到O(nlogn)O(n\log n),由于插入操作本身的时间复杂度是O(n)O(n)

选择排序

思路:每次选择数组的最小值,放入有序部分的末端。该操作通过swap实现,因此不是稳定排序算法。

  • 平均复杂度 O(n2)O(n^2)
  • 最坏复杂度 O(n2)O(n^2)
  • 不稳定

优化思路:堆排序,使用堆维护数组的最小值,平均和最坏复杂度优化为O(nlogn)O(n\log n)

归并排序

思路:分治思想,数组分为左右两块子数组,递归对左右两块进行归并排序后,合并做左右两块子数组。

  • 平均复杂度 O(nlogn)O(n\log n)
  • 最坏复杂度 O(nlogn)O(n\log n)
  • 稳定

注意归并排序的空间复杂度是O(n)O(n),由于在合并操作中需要使用临时数组。

归并排序可用于处理逆序对问题: 剑指 Offer 51. 数组中的逆序对

快速排序

思路:分治思想,数组通过partition分左右两块,递归调用快排处理子块。快排不需要合并操作。

  • 平均复杂度 O(nlogn)O(n\log n)

  • 最坏复杂度 O(n2)O(n^2)

  • 不稳定

快排主要操作是partition的写法,其目的是将数组分块,同时满足两块之间相对大小关系。Wiki: quicksort 给出了几种写法,这里粘贴过来并分析。

选择末尾元素作为主元,返回分割位置。

Lomuto partition scheme:
algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i

可以通过两种方式卡时间复杂度到O(n2)O(n^2):

  1. 数组有序,例如[1, 2, 3, 4, 5] 此时partition结束后分割的两块元素个数为0, n - 1。对应计算次数为n+(n1)+(n2)++1n + (n - 1) + (n - 2) + \cdots + 1

  2. 数组重复元素过多,例如[1, 1, 1, 1, 1] ,分割情况与上一条一致。

通过双指针实现partition,对于重复元素过多的情况,下面算法可以得到大小相近的分块,例如[1, 1, 1, 1, 1] 在第一次被分块为[1, 1], [1, 1],可优化时间复杂度。但是双指针问题存在太多不必要的交换,进一步优化可以参考三路快排。对于接近有序数组,时间复杂度仍会退化到O(n2)O(n^2)

Hoare partition scheme:
algorithm partition(A, lo, hi) is
    pivot := A[ floor((hi + lo) / 2) ]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot
        do
            j := j - 1
        while A[j] > pivot
        if i ≥ j then
            return j
        swap A[i] with A[j]

针对接近有序数组,为了保证分块大小尽可能接近,最好方法可使用数组中位数作为主元,另外可使用随机化方法优化,其思路是随机选择一个元素作为主元,推荐查看 排序数组 官方题解 中的快排算法写法。

补充:使用数组中位数作为主元,存在最坏时间复杂度为O(nlogn)O(n\log n)的快速排序算法。详见BFPRT

计数排序

思路:空间换时间,使用数组值域大小的计数数组对待排序数组元素进行计数。

  • 平均时间复杂度 O(n+w)O(n + w) ww 为值域大小
  • 最坏时间复杂度 O(n+w)O(n + w)
  • 稳定

每日一题问题汇总

LeetCode0132 分割回文串 II 为什么 g 的初始值可以都初始化为 true?

可以看一下题解列出的状态转移方程。在进行计算过程中,不成立的部分会变成 false。另外全初始化成 false 也没有问题,只要最终的状态和定义状态一致。例如可以这样写,定义valid[i][j]表示ij构成的字符串是回文串,i > j时为false

vector<vector<bool>> valid(n, vector<bool>(n, false));
        for(int i = 0; i < n; ++i)
            valid[i][i] = true;
        // i > j False
        for(int len = 2; len <= n; ++len){
            for(int i = 0; i + len - 1 < n; ++i){
                int j = i + len - 1;
                if (len == 2){
                    if(s[i] == s[j])
                        valid[i][j] = true;
                    continue;
                }
                if (s[i] == s[j]) valid[i][j] = valid[i + 1][j - 1];
            }
        }

LeetCode0132 分割回文串 II 。能看懂题解里面关于 f [i]f [j] 的递推,但看不懂代码

int[] f = new int[n];
        Arrays.fill(f, Integer.MAX_VALUE);
        for (int i = 0; i < n; ++i) {
            if (g[0][i]) {
                f[i] = 0;
            } else {
                for (int j = 0; j < i; ++j) {
                    if (g[j + 1][i]) {
                        f[i] = Math.min(f[i], f[j] + 1);
                    }
                }
            }
        }

f[i] 表示的是从开始到位置i 的最小切割次数。g[i][j] 的意思在位置i, j构成的子串是否为回文。如果g[0][i] 为真,那么到位置i的切分次数为0, 即f[i] = 0, 因为已经是回文串了。
否则要枚举[k][i] k = 0,1,....., i -1 来计算最小切割次数。
需要保证最后一次切割为回文,所以最小切割次数应该为:

min(f[k]+1)k[0,i) and g[k+1][i]==truemin(f[k] + 1) \quad k\in[0, i)\ and\ g[k + 1][i] == true

LeetCode1047 删除字符串中的所有相邻重复项 if stk and stk [-1] == ch 有没有大佬给解释一下这行代码的意思

Python 空的列表、字符串布尔值都是Falsestk[-1] 表示的是列表的最后一个元素,在这里意为栈顶。这句代码等价于:

if len(stk) > 0 and stk[len(stk) - 1] == ch:

LeetCode0224 基本计算器 num = num * 10 + s[i] - '0'; 这一步写成 num = num * 10 +(int)s[i] ; ,为什么不行哦?

LeetCode0224 基本计算器 num = num * 10 + s [i] - '0'; 大哥们 -'0' 是啥意思啊

在C++语言 '1' 对应ascii 不是 1。 但是字符'0''9' 的ascii是连续的,所以应该是s[i] - '0'
python可以使用 int(s[i]) 这实际上类似stoi操作。

对于该代码最好写为:

num = num * 10 + (s[i] - '0')

原因是可能存在测试用例(如基本计算器II),在不加括号限定优先级时,num * 10 + s[i] 溢出。

另外该代码是字符串转整数的代码,考虑'1234',按照扫描顺序,改循环依次生成1, 10 + 2 = 12, 120 + 3 = 123, 1230 + 4 = 1234

LeetCode0224 基本计算器 为什么要用 long num = 0,最后 long num 又被转换成为了 int,这样不会有问题吗? 我尝试了用 int num,但是报错了。

c++题解就是int 呀。可能int会存在溢出的问题吧,用long防止这个问题。
如果最后答案在int范围内的话,longint是不受影响的,否则会受到影响。

LeetCode0227 基本计算器IIhxdm,我的代码对于样例一自测输出 1,但提交后却是 4。有人知道为啥吗?

共性问题,如果提交结果和本地运行不一致,通常是成员变量或者全局变量的问题,注意这种变量每次调用函数时都要重新初始化。

LeetCode0331 验证二叉树的前序序列化 这种解法是不是对前序、中序和后序都适用啊

不是的,考虑中序遍历,对于一个节点的树,遍历结果是#,1,#

LeetCode0331 验证二叉树的前序序列化 真诚发问,如何理解槽位这个解释? 看了半天没看懂

槽位可以理解为当前可容纳的节点的容量,当增加一个非空节点的时候,会消耗掉一个槽位,同时增加两个槽位 (新增节点的左右子节点的位置)。 增加空节点的时候,由于空节点只能是叶子节点,只会消耗掉一个槽位,而不会增加槽位。

初始化为1个槽位,用于放置根节点。

LeetCode0705 设计哈希集合 为什么是 769 啊 dalao 们

因为 769 是质数。可以换一个接近的质数也可以。可以参考Good hash table primes

10
共 3 个回复

很棒

好活

学长好耶!