0%

二分查找

二分查找可以实现 O(logn) 的时间复杂度,直观一点说,2 的 32 次方,大概 42 亿,最多需要比较 32 次就可以查找到数据。二分查找的原理就是,每次都将数据一分为二,通过被查找元素和中间的元素对比,判定下次查找是在中点的左边还是右边,即将待查找的区间缩小为之前的一半,直到找到要查找的元素。

使用二分查找的约束条件

  • 依赖数组
    • 二分查找需要按照下标随机访问首、尾、中间的元素所以需要数组,如果基于链表实现,时间复杂度会从 O(logn) 退化成 O(n) 的
    • 因为是基于数组的,所以内存空间是连续的,大数据量的情况下可能会没有那么大连续内存
  • 数据是有序的
    • 数据必须是有序的,如果数据没有序,首先需要先排序
    • 适用于查多改少的场景,因为要维护数据的有序性,插入、删除操作的复杂度会很高

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int binarySearch(int[] array, int target) {
int left = 0, right = array.length - 1, mid;
while (left <= right) {
mid = (right - left) / 2 + left;
if (array[mid] == target) {
return mid;
} else if (array[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}

变体问题

  • 有序数据集合中存在重复的数据,找到 第一个 / 最后一个 等于给定值的数据
  • 搜索旋转排序数组

总结

本周的学习内容还包含 DFS、BFS 这个两个已经老生常谈的算法了。我们之前在练习二叉树的前、中、后序遍历的时候就是深度遍历,全排列、组合、子集、生成括号等回溯算法解决问题的时候也是深度优先遍历。练习二叉树层序遍历、全排列、岛屿数量可以用广度优先解决,有时候用广度优先能解决的问题用深度优先也可以解决,因为在深度优先遍历的时候,我们是知道遍历的深度 level 的。通常情况下,用迭代法解决深度优先遍历会用到 ,因为栈可以方便我们回溯到上个节点继续遍历。迭代法解决广度优先遍历会用到 队列,我们将每一层的节点入队,并遍历 poll 出当前层的所有节点,依次处理,如果处理的当前层的节点还有下层节点,再次入队,往复处理直到队列为空。

关于贪心算法,打算在下下周学完动态规划一起总结,这个是继 分治回溯 后的最后两个算法思想。全部学完后,可以比较一下它们的异同,解决问题的适用范围。

二分查找可以实现 O(logn) 的时间复杂度,但是这个是有前提的。首要需要使用数组保持数据,即可随机访问、内存连续的;其次数据要是有序的,所以插入、删除数据时,为了保持有序需要付出额外的代价,或者说需要对数据进行排序,也就是说二分查找比较适查多写少的场景。最后要理解记忆二分查找的代码模板,能够用二分查找解决一些变体情况。

递归

递归,去的过程叫“递”,回的过程叫“归”。能够用递归解决的问题都需要满足如下几个条件:

  • 存在递归终止条件
  • 一个问题可以分解为多个子问题
  • 问题和子问题,除了处了的数据规模不同,解决思路完全相同

我们需要找到将大问题分解为小问题的规律,并且基于此写抽象成一个递推公式,这个过程要注意,不要试图用人脑去分解递归的每个步骤,只要考虑当前层的逻辑。

使用递归还要注意重复计算问题,可以使用字典表缓存已经计算的结果。比方说爬楼梯问题暴力递归的时间复杂度是 O(2^n) ,在使用缓存之后时间复杂度就是 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 递归代码模板
**/
public void recur(int level, int param) {
// 终结者
if (level > MAX_LEVEL) {
// process result
return;
}

// 当前层逻辑
process(level, param);

// 下一层
recur(level + 1, newParam);

// 重置当前状态
}

分治

分治就是“分而治之”,将原问题划分成 n 个规模较小而结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原问题的解。用分治思想解决问题需要具有如下条件:

  • 原问题与分解成的小问题具有相同的模式

  • 原问题分解成的子问题可以独立求解,子问题之间没有相关性不会相互影响

  • 具有分解终止条件,也就是说,当问题足够小时,可以直接求解

  • 可以将子问题合并成原问题,但合并操作的复杂度不能太高,否则算法总体复杂度无法减小分

分治思想的代码包括 3 个步骤,分解、解决、合并:

  • 分解:将原问题分解为一系列子问题

  • 解决:递归地求解各个子问题,若子问题足够小,则直接求解

  • 合并:将子问题的结果合并成原问题的解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* 分治代码模板
* 求多数元素
**/
private int majorityElementRec(int[] nums, int low, int high) {
// Step1: 最小子问题, 可直接得出结果, 也是递归终止条件
// 这里就是将数组分解成只有一个元素
if (low == high) {
return nums[low];
}

// Step2: 准备数据
// 这里将数据一切为二
int mid = (high - low) / 2 + low;

// Step3: 问题分解并求出子问题
// 这里是分别求出左多数和右多数
int left = majorityElementRec(nums, low, mid);
int right = majorityElementRec(nums, mid + 1, high);

// Step4: 合并结果, 得出最终结果
// 这里是返回左右两边数量最多的数
if (left == right) {
return left;
}
int leftCount = countInRange(nums, left, low, high);
int rightCount = countInRange(nums, right, low, high);
return leftCount > rightCount ? left : right;

// Step5: 恢复状态
}

回溯

回溯就是采用试错的思想,从一组可能的解中,选择出一个满足要求的解。

  • 穷举所有的解,找到满足要求的解
    • 通过将问题分解为多个阶段(步骤),来穷举所有的可能解
    • 通过尝试发现当前的阶段的答案不能得到正确的解,将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的解
  • 利用剪枝操作,排除不需要穷举的情况,从而提高效率

总结

递归是解决问题一种手段属于编程技巧,而分治、回溯、贪心算法、动态规划属于算法思想。他们的关键是都是要找到问题的重复性。

分治思想的核心就是分而治之。在工程实践中 MapRedue 的本质就是分治,比方说 Spark 解决单机节点性能问题,将任务拆分到多个机器上处理,子任务之间互不干扰独立计算,最后再将合并结果。

回溯相当于穷举所有的情况,然后对比得到最优解。回溯算法的时间复杂度非常高,是指数级别。可以利用剪枝操作,排除不需要的分支,从而提高效率。

本周的算法思想并不难理解,关键是解决问题的时候能够找出问题的重复性,并且能够分解出子问题。“思想”总是高度抽象,想要灵活运用还是要多多练习这类的题目。

哈希表

哈希表的本质就用数组支持按照下标随机访问的特性,实现查找、删除、插入数据的时间复杂度为 O(1) 。哈希函数就是将 Key 转换为数组下标,将数据存放到指定位置。

哈希函数的本质就是取余操作,能将任何 Key,转换为有限范围内的一个数值。比方说任意大的正整数对 5 取余那么结果就是在 [0, 4] 。同理著名的 MD5 哈希函数,对任意长度的输入,其输出都是 128 bit,即 16 字节。

JDK 中 HashMap 将 Key 映射到哈希表数组下标方法是 tab[i = (n - 1) & hash] ,其实就是 tab[i = hash % n]tab 就存放数据的数组 tablehash = key.hashCode() ^ (key.hashCode() >>> 16) 就 Key 的哈希值,n 就是哈希表的数组长度,翻译过来就是将 key 的哈希值对数组长度 - 1进行取余,结果作为数组下标存放数据。

由于数组的存储空间有限,很容易产生哈希碰撞,即不同的 Key 哈希出的数据下标是一样的,如果直接将数据存入数组中,会导致数据存储丢失。HashMap 中将数组称作为 bucket array(桶数组), 每个桶都会对应一条链表,将哈希值相同的元素都放到相同桶对应的链表中,来解决 Hash 碰撞的问题。

哈希表存放数据的位置完全是根据哈希函数的计算来的,所以数据的存放是无序的。即使在 LinkedHashMap 中通过双向链表,实现插入的顺序、或访问的 LRU, 但是还是无法做到对数据的排序,直观一点说就是无法直接获取 “> n” 的数据。

二叉树

树是在数组或链表的基础上赋予了节点位置信息,所谓的升维思想。

几种特殊的二叉树:

  • 在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值,这就是二叉搜索树

  • 叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点,这就是满二叉树

  • 如果满二叉树,叶子节点虽然没有排满,但是叶子节点都靠左排列,这就是完全二叉树

  • 约束完全二叉树每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值,这就是

二叉树的遍历

二叉树的遍历分为前序遍历、中序遍历、后序遍历这些都属于深度优先(DFS),层次遍历属于广度优先(BFS)。在 LeetCode 上这几种遍历题目都有,树的遍历递归写法最为清晰明了,栈的写法比较容易写废,我刷了 3 遍,才写熟练。为了方便理解,我把几种遍历的栈图画出来了,方便理解。

前序遍历
中序遍历
后序遍历

堆是一种特殊的二叉树 - 完全二叉树。在上周的课程,课后作业分析 PriorityQueue 其实就带着学习了堆的特性。以小顶堆为例子,查找最小是 O(1)、删除最小是 O(logn),插入是 O(logn) 或是 O(1)。在堆中插入、删除数据为了维护最小元素在堆顶,分别涉及上浮、下沉的元素交换操作。

堆的应用场景有优先级队列,比方说 JDK 中的 PriorityQueue 。利用优先级队列我们可以解决 K 个有序数列合并 问题,将数列全部加入堆中,再依次取出即可。如果是将 K 个小文件合并成一个大文件,且内存中无法存放全部结果,可以依次从 K 个文件读取并删除第一个元素并放入堆中,然后取出堆顶的元素,放入合并文件中,再找到刚才堆顶元素对应的文件,读取并删除下一个元素,放入堆中,直到堆中无任何元素,合并任务就完成了。优先级队列还有个场景就是 延时/定时任务队列 ,我们可以维护一个小顶堆,将到期时间早的放在堆顶,定时检查堆顶元素就可以知道整个队列有没有任务到期,避免了对整个队列的轮询检查,提高了性能。

堆还常用于解决 Top K 问题,根据不同的场景用大顶堆或小顶堆,并保证堆的大小为 K,Top K 就是堆中所有的元素。

总结

这两周的学习,发现数据的存储结构只有两种:数组、链表,他们就是构成计算机数据结构的 “基本粒子”,其他的数据结构只是在其基础上演进。栈、队列、哈希表、树、图底层实现都是数组或链表,或者两者都可以实现。

升维的本质就是给数据的位置增加特殊的位置含义。比方说,树用数组存放,当根的数组下标是 i (i > 0) ,那么左孩子的下标就是 i * 2,右孩子的下标就是 i * 2 + 1

哈希表已经能做到对数据的查找、删除、插入 O(1) 的时间复杂度了,但是数据存储是无序的,不支持有序输出。如果使用二叉搜索树,我们只需要中序遍历,就是序输出了。

当向二叉搜索树有序插入一堆数据时候,二叉搜索树就会显得极度不平衡,退化成了链表,查找从 O(logn) 退化为 O(n),所以又有了平衡二叉查找树 - 红黑树,它能够始终保持在 O(logn) 。

二叉搜索树和堆又有什么关系呢?我们通过对二叉搜索树的中序列遍历可以得到一个有序序列,堆可以通过不断的从堆顶 poll 数据得到一个有序序列,这就是的堆排序;二叉搜索树会有退化不平衡的现象,而堆却不会;二叉搜索树获取最大或最小值都是 O(logn) ,但堆需要根据是大顶堆还是小顶堆才能获取最大值、还是最小值并且时间复杂是 O(1) 。

本周的时间实在是不够用的,关于堆、图的题目都还没有练习,下周的课程又开始了,要再加加油了~~