Words count
424 字
Reading time
2 分钟
引论
**选择问题（确定N个数中第k大的数）**
两种“直观算法”：
- 算法1：将N个数读入数组，用冒泡排序等方法递减排序，直接返回第k个元素。
- 算法2：先读前k个元素并递减排序；再逐个读剩余元素，若新元素≥数组第k个，就插入到数组正确位置（同时挤出一个元素），最终返回数组第k个元素。
效率缺陷： 用“100万个元素、k=50万”模拟时，这两种算法需“计算机处理若干天”才能完成；后续会介绍更高效的算法，能在“一秒左右”得到结果。 由此说明：这两种直观算法虽能得到正确结果，但效率过低，不是“好算法”。
字谜问题（在二维字母数组中找单词）
输入是由字母和单词组成的二维数组，需找出水平、垂直或对角线方向存在的单词（如图1-1示例，包含 this、two、fat、that 等单词）。
两种“直观算法”：
- 算法1：对单词表中的每个单词，检查所有“(行, 列, 方向)”的三元组，验证是否存在该单词（需大量嵌套
for循环）。 - 算法2：对每个“(行, 列, 方向, 字符数)”的四元组，测试对应的单词是否在单词表中（同样需大量嵌套
for循环）。
Tuntun Yuchiha