企业官网建设流程全解析

习题一、合并k个有序序列—最小堆

问题描述：合并k个有序序列

假设你有k kk个已经排好序的序列，需要将它们合并成一个有序序列。

示例：

• 序列1：[ 1 , 4 , 7 , 10 ] [1, 4, 7, 10][1,4,7,10]
• 序列2：[ 2 , 5 , 8 ] [2, 5, 8][2,5,8]
• 序列3：[ 3 , 6 , 9 , 11 ] [3, 6, 9, 11][3,6,9,11]

目标：合并成[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 ] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11][1,2,3,4,5,6,7,8,9,10,11]

使用最小堆

核心思想：用最小堆维护k kk个序列的当前首元素，每次取出堆顶（最小值），然后从对应序列取下一个元素加入堆。

1. 堆中放入每个序列的首元素，堆顶即是最小值
2. 取出对应的下一个元素，放入堆（会进行排序）

为什么用堆？

• 找最小值：堆顶就是最小值，O ( 1 ) O(1)O(1)时间
• 插入元素：插入堆并调整，O ( lg ⁡ k ) O(\lg k)O(lgk)时间
• 删除堆顶：删除并调整，O ( lg ⁡ k ) O(\lg k)O(lgk)时间

总时间复杂度：O ( n lg ⁡ k ) O(n \lg k)O(nlgk)✅

算法步骤

步骤1：初始化堆

取出k kk个子序列的首元素，构成一个最小堆。

每个堆元素需要记录：

• 值：元素的值
• 来源：来自哪个序列（序列编号），以及在该序列中的位置（索引）

步骤2：重复提取和插入

1. 取出堆顶元素：这是当前所有序列中的最小值
2. 加入结果序列
3. 从对应序列取下一个元素：如果该序列还有元素，将下一个元素加入堆
4. 调整堆：维护堆的性质

单次操作复杂度：O ( lg ⁡ k ) O(\lg k)O(lgk)

因为堆中最多同时有k个元素，而调整堆的时间复杂度与堆的高度成正比，高度为log₂k，所以是O(lg k)。

步骤3：直到所有元素处理完

重复步骤2，直到：

• 所有子序列都为空
• 堆也为空

总操作次数：n nn次（每个元素处理一次）

总时间复杂度：n × O ( lg ⁡ k ) = O ( n lg ⁡ k ) n \times O(\lg k) = O(n \lg k)n×O(lgk)=O(nlgk)✅

📊 算法复杂度分析

分析：

• 初始化堆：将k kk个元素加入堆，时间复杂度O ( k lg ⁡ k ) O(k \lg k)O(klgk)
• 主循环：处理n nn个元素，每次操作包括：
  • 取出堆顶：O ( lg ⁡ k ) O(\lg k)O(lgk)
  • 插入新元素：O ( lg ⁡ k ) O(\lg k)O(lgk)
  • 总时间：O ( n lg ⁡ k ) O(n \lg k)O(nlgk)

总时间复杂度：O ( k lg ⁡ k ) + O ( n lg ⁡ k ) = O ( n lg ⁡ k ) O(k \lg k) + O(n \lg k) = O(n \lg k)O(klgk)+O(nlgk)=O(nlgk)

说明：当n ≥ k n \geq kn≥k时（通常情况），O ( n lg ⁡ k ) O(n \lg k)O(nlgk)是主导项。

💡记忆口诀：k个序列要合并，最小堆来帮忙，每次取出堆顶值，对应序列补新元，n次操作lgk，总复杂度nlgk！

习题二、O(n)时间排序n个整数—基数排序

问题描述：在O(n)时间内排序

关键约束：

• 元素个数：n nn
• 值域范围：[ 0 , n 2 − 1 ] [0, n^2-1][0,n2−1]
• 时间复杂度要求：O ( n ) O(n)O(n)

为什么不能用常规排序？

• 比较排序（快速排序、归并排序等）：下界是O ( n lg ⁡ n ) O(n \lg n)O(nlgn)，不符合要求
• 计数排序：值域是[ 0 , n 2 − 1 ] [0, n^2-1][0,n2−1]，需要O ( n 2 ) O(n^2)O(n2)空间，时间复杂度O ( n + n 2 ) = O ( n 2 ) O(n + n^2) = O(n^2)O(n+n2)=O(n2)，不符合要求

✅ 正确思路：基数排序 + 计数排序

核心思想

将每个数转换成n nn进制的两位整数，然后使用基数排序。

关键观察

对于任意数a ∈ [ 0 , n 2 − 1 ] a \in [0, n^2-1]a∈[0,n2−1]，可以表示为：
a = p ⋅ n + q a = p \cdot n + qa=p⋅n+q

其中：

• p pp是高位（n nn进制下的十位），0 ≤ p ≤ n − 1 0 \leq p \leq n-10≤p≤n−1
• q qq是低位（n nn进制下的个位），0 ≤ q ≤ n − 1 0 \leq q \leq n-10≤q≤n−1

为什么这样表示？

• a aa的最大值是n 2 − 1 n^2-1n2−1
• p ⋅ n + q p \cdot n + qp⋅n+q的最大值是( n − 1 ) ⋅ n + ( n − 1 ) = n 2 − n + n − 1 = n 2 − 1 (n-1) \cdot n + (n-1) = n^2 - n + n - 1 = n^2 - 1(n−1)⋅n+(n−1)=n2−n+n−1=n2−1✅

算法步骤

步骤1：将每个数转换为n进制两位表示

对于每个数a aa，计算：

• p = ⌊ a / n ⌋ p = \lfloor a / n \rfloorp=⌊a/n⌋（高位）
• q = a m o d n q = a \bmod nq=amodn（低位）

步骤2：使用基数排序

基数排序按从低位到高位的顺序排序：

1. 第一轮：基于低位q qq的值进行排序（使用计数排序）
2. 第二轮：基于高位p pp的值进行排序（使用计数排序）

为什么先排低位再排高位？

• 基数排序的稳定性要求：相同高位时，保持低位的相对顺序
• 先排低位，后排高位，可以保证最终结果正确

步骤3：时间复杂度分析

• 计数排序：时间复杂度O ( n + k ) O(n + k)O(n+k)，其中k kk是值域大小
• 第一轮（基于q qq）：k = n k = nk=n，时间O ( n + n ) = O ( n ) O(n + n) = O(n)O(n+n)=O(n)
• 第二轮（基于p pp）：k = n k = nk=n，时间O ( n + n ) = O ( n ) O(n + n) = O(n)O(n+n)=O(n)
• 总时间：O ( n ) + O ( n ) = O ( n ) O(n) + O(n) = O(n)O(n)+O(n)=O(n)✅

📊 算法复杂度分析

分析：

• 转换阶段：将每个数转换为n进制两位，O ( n ) O(n)O(n)
• 第一轮计数排序（基于q qq）：值域[ 0 , n − 1 ] [0, n-1][0,n−1]，O ( n + n ) = O ( n ) O(n + n) = O(n)O(n+n)=O(n)
• 第二轮计数排序（基于p pp）：值域[ 0 , n − 1 ] [0, n-1][0,n−1]，O ( n + n ) = O ( n ) O(n + n) = O(n)O(n+n)=O(n)

总时间复杂度：O ( n ) + O ( n ) + O ( n ) = O ( n ) O(n) + O(n) + O(n) = O(n)O(n)+O(n)+O(n)=O(n)✅

💡 拓展思考

1. 为什么值域必须是[ 0 , n 2 − 1 ] [0, n^2-1][0,n2−1]？

   • 这样才能用n nn进制两位表示
   • 如果值域更大，需要更多位数，时间复杂度会增加

2. 如果值域是[ 0 , n 3 − 1 ] [0, n^3-1][0,n3−1]怎么办？

   • 需要3位n nn进制数
   • 需要3轮计数排序
   • 时间复杂度仍然是O ( n ) O(n)O(n)（因为每轮值域都是n nn）

3. 实际应用：

   • 整数排序：当值域范围合适时，比比较排序更快
   • 字符串排序：可以看作多进制数的排序
   • 日期排序：年月日可以看作多位数

4. 与其他排序对比：

   • 比较排序：O ( n lg ⁡ n ) O(n \lg n)O(nlgn)，通用但较慢
   • 计数排序：值域大时空间复杂度高
   • 基数排序：值域合适时，可以达到O ( n ) O(n)O(n)

💡记忆口诀：n个整数n²值域，n进制两位来转换，基数排序两轮走，计数排序O(n)，总复杂度O(n)！

习题三、判断是否存在两数乘积等于k—哈希表

问题描述：O(n)时间判断两数乘积

哈希表方法

核心思想

对于每个元素a i a_iai​，如果k kk能被a i a_iai​整除，计算a j = k / a i a_j = k / a_iaj​=k/ai​，然后在数组中查找是否存在a j a_jaj​。

关键技巧：使用哈希表实现O ( 1 ) O(1)O(1)的查找。

算法步骤

步骤1：构建哈希表

对于数组中的每个元素a i a_iai​：

• 如果k m o d a i = 0 k \bmod a_i = 0kmodai​=0（即k kk能被a i a_iai​整除）
• 计算a j = k / a i a_j = k / a_iaj​=k/ai​
• 将( a j , ( a i , a j ) ) (a_j, (a_i, a_j))(aj​,(ai​,aj​))存入哈希表
  • 键：a j a_jaj​（我们希望在数组中找到的值）
  • 值：( a i , a j ) (a_i, a_j)(ai​,aj​)（一对可能的解）

时间复杂度：遍历n nn个元素，每次操作O ( 1 ) O(1)O(1)，总计O ( n ) O(n)O(n)

步骤2：查找匹配

对于数组中的每个元素a x a_xax​：

• 检查哈希表中是否存在键a x a_xax​
• 如果存在，说明找到了匹配： 哈希表中存储的是( a x , a y ) (a_x, a_y)(ax​,ay​)， 这意味着存在a x × a y = k a_x \times a_y = kax​×ay​=k，返回( a x , a y ) (a_x, a_y)(ax​,ay​)

时间复杂度：遍历n nn个元素，每次哈希查找O ( 1 ) O(1)O(1)，总计O ( n ) O(n)O(n)

步骤3：返回失败

如果步骤2中没有找到任何匹配，返回"失败"。

时间复杂度：O ( 1 ) O(1)O(1)

📊 算法复杂度分析

分析：

• 步骤1：遍历n nn个元素，每次：

  • 检查整除性：O ( 1 ) O(1)O(1)
  • 计算除法：O ( 1 ) O(1)O(1)
  • 哈希表插入：平均O ( 1 ) O(1)O(1)
  • 总计：O ( n ) O(n)O(n)

• 步骤2：遍历n nn个元素，每次：

  • 哈希表查找：平均O ( 1 ) O(1)O(1)
  • 总计：O ( n ) O(n)O(n)

• 步骤3：O ( 1 ) O(1)O(1)

总时间复杂度：O ( n ) + O ( n ) + O ( 1 ) = O ( n ) O(n) + O(n) + O(1) = O(n)O(n)+O(n)+O(1)=O(n)✅

注意：这是平均情况下的时间复杂度。最坏情况下（所有元素哈希冲突），时间复杂度可能退化到O ( n 2 ) O(n^2)O(n2)，但通过良好的哈希函数可以避免。

💡 拓展思考

1. 为什么需要检查k m o d a i = 0 k \bmod a_i = 0kmodai​=0？
   • 确保a j = k / a i a_j = k/a_iaj​=k/ai​是整数
   • 数组中都是整数，非整数不可能存在
2. 如果允许i = j i = ji=j怎么办？
   • 需要检查a i 2 = k a_i^2 = kai2​=k的情况
   • 确保数组中a i a_iai​出现至少2次
3. 与其他方法对比：
   • 暴力枚举：O ( n 2 ) O(n^2)O(n2)，慢但简单
   • 排序+双指针：O ( n lg ⁡ n ) O(n \lg n)O(nlgn)，需要排序
   • 哈希表方法：O ( n ) O(n)O(n)，最快但需要额外空间

💡记忆口诀：两数乘积等于k，哈希表来帮忙，先算a j a_jaj​存表里，再查a x a_xax​在不在，两轮遍历O(n)，总复杂度O(n)！