企业官网建设流程全解析

wordpress公司网站插件,ftp媒体库wordpress,小程序制作模板网站,wordpress站点标题图片文章目录习题一、合并k个有序序列—最小堆问题描述#xff1a;合并k个有序序列使用最小堆为什么用堆#xff1f;算法步骤步骤1#xff1a;初始化堆步骤2#xff1a;重复提取和插入步骤3#xff1a;直到所有元素处理完#x1f4ca; 算法复杂度分析习题二、O(n)时间排序n个…文章目录习题一、合并k个有序序列—最小堆问题描述合并k个有序序列使用最小堆为什么用堆算法步骤步骤1初始化堆步骤2重复提取和插入步骤3直到所有元素处理完 算法复杂度分析习题二、O(n)时间排序n个整数—基数排序问题描述在O(n)时间内排序✅ 正确思路基数排序 计数排序核心思想关键观察算法步骤步骤1将每个数转换为n进制两位表示步骤2使用基数排序步骤3时间复杂度分析 算法复杂度分析 拓展思考习题三、判断是否存在两数乘积等于k—哈希表问题描述O(n)时间判断两数乘积哈希表方法核心思想算法步骤步骤1构建哈希表步骤2查找匹配步骤3返回失败 算法复杂度分析 拓展思考习题一、合并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个序列的当前首元素每次取出堆顶最小值然后从对应序列取下一个元素加入堆。堆中放入每个序列的首元素堆顶即是最小值取出对应的下一个元素放入堆会进行排序为什么用堆找最小值堆顶就是最小值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重复提取和插入取出堆顶元素这是当前所有序列中的最小值加入结果序列从对应序列取下一个元素如果该序列还有元素将下一个元素加入堆调整堆维护堆的性质单次操作复杂度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(nn2)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 qap⋅nq其中p pp是高位n nn进制下的十位0 ≤ p ≤ n − 1 0 \leq p \leq n-10≤p≤n−1q qq是低位n nn进制下的个位0 ≤ q ≤ n − 1 0 \leq q \leq n-10≤q≤n−1为什么这样表示a aa的最大值是n 2 − 1 n^2-1n2−1p ⋅ n q p \cdot n qp⋅nq的最大值是( 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−nn−1n2−1✅算法步骤步骤1将每个数转换为n进制两位表示对于每个数a aa计算p ⌊ a / n ⌋ p \lfloor a / n \rfloorp⌊a/n⌋高位q a m o d n q a \bmod nqamodn低位步骤2使用基数排序基数排序按从低位到高位的顺序排序第一轮基于低位q qq的值进行排序使用计数排序第二轮基于高位p pp的值进行排序使用计数排序为什么先排低位再排高位基数排序的稳定性要求相同高位时保持低位的相对顺序先排低位后排高位可以保证最终结果正确步骤3时间复杂度分析计数排序时间复杂度O ( n k ) O(n k)O(nk)其中k kk是值域大小第一轮基于q qqk n k nkn时间O ( n n ) O ( n ) O(n n) O(n)O(nn)O(n)第二轮基于p ppk n k nkn时间O ( n n ) O ( n ) O(n n) O(n)O(nn)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(nn)O(n)第二轮计数排序基于p pp值域[ 0 , n − 1 ] [0, n-1][0,n−1]O ( n n ) O ( n ) O(n n) O(n)O(nn)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)✅ 拓展思考为什么值域必须是[ 0 , n 2 − 1 ] [0, n^2-1][0,n2−1]这样才能用n nn进制两位表示如果值域更大需要更多位数时间复杂度会增加如果值域是[ 0 , n 3 − 1 ] [0, n^3-1][0,n3−1]怎么办需要3位n nn进制数需要3轮计数排序时间复杂度仍然是O ( n ) O(n)O(n)因为每轮值域都是n nn实际应用整数排序当值域范围合适时比比较排序更快字符串排序可以看作多进制数的排序日期排序年月日可以看作多位数与其他排序对比比较排序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)步骤3O ( 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)但通过良好的哈希函数可以避免。 拓展思考为什么需要检查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​是整数数组中都是整数非整数不可能存在如果允许i j i jij怎么办需要检查a i 2 k a_i^2 kai2​k的情况确保数组中a i a_iai​出现至少2次与其他方法对比暴力枚举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)