Ha$p^3$lanet

前面介绍了两种使用随机算法（快速排序 和 随机选择算法），特点是每次执行的 时间复杂度不确定，但能够确定的得到正确的解。本篇中同样介绍一种随机算法 - Karger 算法， 用于求解 “最小割问题”。与前面几种随机算法不同的是，Karger 算法的时间复杂度是确定的，但得到的解不一定是正确的，然而，我们可以通过 多次 调用的方法，来提升得到正确解的概率。

在本篇文章中，我们将重点分析快速排序算法的时间复杂度。

本文是系列算法课程的笔记，课程地址。前面一篇博客 介绍了主定理和几个分治算法的例子。这里再补充两个例子，并用代码对分治算法的实现进行说明。

二分查找可以以 O(logn) 的时间复杂度完成查找，最典型的二分查找问题是在一个排序数组中，查找特定的值，返回其下标。实际中，二分查找问题有着很多的变形，这里以一道典型的题目展示二分查找的一些典型变化。

前段时间总结过一篇介绍通过 HashMap 提升查找效率的文章，实际上，这类问题代码通常并不复杂，难点常常是设计 HashMap 的 key 值上。leetcode 247场周赛的一道题目 1915. 最美子字符串的数目 就是一个典型的需要使用一些技巧来设计 HashMap 的 key 的问题。

Top k 问题是一个经典的算法问题，要求求解数组中第 k 大（or 第k小的元素）。最简单的，该问题可以通过排序来解决，算法的时间复杂度为 O(nlogn)。有没有效率更高的算法呢？

leetcode 周赛中遇到的一道需要使用 字典树的题目，总结分析一下。

对于数据结构 HashMap/HashSet，它不仅可以用于去重，还可以用于快速查找（复杂度 O(1)）。针对查找功能，整理了下面几道题目，用于体会其用法。

leetcode 周赛题 1916. 统计为蚁群构筑房间的不同顺序 比较有趣，需要使用 树形动态规划的方法进行解决。

本文针对一个典型的 bfs 问题进行分析。