企业官网建设流程全解析

如何做电商网站,如何建设网站简介,上海传媒公司有哪些,泰兴市城乡建设管理局网站Java版LeetCode热题100之寻找两个正序数组的中位数#xff1a;从暴力到最优解的全面解析 本文将深入剖析 LeetCode 第4题「寻找两个正序数组的中位数」#xff0c;通过多种解法、复杂度分析、面试技巧与实际应用#xff0c;带你彻底掌握这道被誉为“LeetCode最难”的经典算法…Java版LeetCode热题100之寻找两个正序数组的中位数从暴力到最优解的全面解析本文将深入剖析 LeetCode 第4题「寻找两个正序数组的中位数」通过多种解法、复杂度分析、面试技巧与实际应用带你彻底掌握这道被誉为“LeetCode最难”的经典算法题。一、原题回顾题目描述LeetCode 4. 寻找两个正序数组的中位数给定两个大小分别为m和n的正序从小到大数组nums1和nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O(log (mn))。示例示例 1输入nums1 [1,3], nums2 [2] 输出2.00000 解释合并数组 [1,2,3] 中位数 2示例 2输入nums1 [1,2], nums2 [3,4] 输出2.50000 解释合并数组 [1,2,3,4] 中位数 (2 3) / 2 2.5约束条件nums1.length mnums2.length n0 m, n 10001 m n 2000-10^6 nums1[i], nums2[i] 10^6二、原题分析这道题的难点在于时间复杂度要求极高O(log(mn))→ 暗示必须使用二分查找不能合并数组合并需要O(mn)时间和空间中位数定义依赖总长度奇偶性奇数第(mn)/2 1小的数偶数第(mn)/2和(mn)/2 1小的数的平均值。关键转化问题可转化为在两个有序数组中找到第 k 小的元素。若mn为奇数 → 找第k (mn)/2 1小的数若mn为偶数 → 找第k1 (mn)/2和k2 (mn)/2 1小的数。✅ 核心挑战如何在O(log k)时间内找到第 k 小的元素三、答案构思方法一二分查找第 k 小元素推荐核心思想每次排除k/2个不可能是第 k 小的元素。比较nums1[k/2-1]和nums2[k/2-1]较小者及其前面的所有元素都不可能是第 k 小因为最多只有k-2个元素比它小排除这些元素更新k递归处理。方法二划分数组更优但更难理解核心思想将两个数组划分为左右两部分使得左半部分长度 右半部分长度或 1左半部分最大值 ≤ 右半部分最小值。通过二分查找合适的划分点直接计算中位数。 方法一更直观方法二时间复杂度更低O(log min(m,n))。四、完整答案Java 实现方法一二分查找第 k 小元素classSolution{publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2){inttotalLengthnums1.lengthnums2.length;if(totalLength%21){// 奇数返回第 (totalLength/2 1) 小的数returngetKthElement(nums1,nums2,totalLength/21);}else{// 偶数返回第 totalLength/2 和 totalLength/21 小的数的平均值return(getKthElement(nums1,nums2,totalLength/2)getKthElement(nums1,nums2,totalLength/21))/2.0;}}/** * 找到两个有序数组中第 k 小的元素k 从 1 开始 */privateintgetKthElement(int[]nums1,int[]nums2,intk){intlen1nums1.length,len2nums2.length;intindex10,index20;// 当前搜索起始位置while(true){// 边界情况1nums1 已遍历完if(index1len1){returnnums2[index2k-1];}// 边界情况2nums2 已遍历完if(index2len2){returnnums1[index1k-1];}// 边界情况3k1返回当前最小值if(k1){returnMath.min(nums1[index1],nums2[index2]);}// 正常情况尝试排除 k/2 个元素inthalfk/2;// 计算新索引防止越界intnewIndex1Math.min(index1half,len1)-1;intnewIndex2Math.min(index2half,len2)-1;intpivot1nums1[newIndex1],pivot2nums2[newIndex2];if(pivot1pivot2){// 排除 nums1[index1 ... newIndex1]k-(newIndex1-index11);index1newIndex11;}else{// 排除 nums2[index2 ... newIndex2]k-(newIndex2-index21);index2newIndex21;}}}}方法二划分数组最优解classSolution{publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2){// 确保 nums1 是较短的数组优化时间复杂度if(nums1.lengthnums2.length){returnfindMedianSortedArrays(nums2,nums1);}intmnums1.length,nnums2.length;intleft0,rightm;// 在 nums1 上二分查找划分点 iintmedian10,median20;// 中位数候选值while(leftright){// i: nums1 左半部分的元素个数// j: nums2 左半部分的元素个数inti(leftright)/2;intj(mn1)/2-i;// 处理边界用极值代替不存在的元素intnums1LeftMax(i0)?Integer.MIN_VALUE:nums1[i-1];intnums1RightMin(im)?Integer.MAX_VALUE:nums1[i];intnums2LeftMax(j0)?Integer.MIN_VALUE:nums2[j-1];intnums2RightMin(jn)?Integer.MAX_VALUE:nums2[j];if(nums1LeftMaxnums2RightMin){// 找到合适的划分median1Math.max(nums1LeftMax,nums2LeftMax);// 左半最大值median2Math.min(nums1RightMin,nums2RightMin);// 右半最小值lefti1;// 尝试更大的 i找最大满足条件的 i}else{// i 太大需要减小righti-1;}}// 根据总长度奇偶性返回结果return(mn)%20?(median1median2)/2.0:median1;}}五、代码分析方法一详解核心逻辑排除不可能的元素为什么可以排除k/2个元素假设A[k/2-1] B[k/2-1]则A[0..k/2-1]中的每个元素都 ≤A[k/2-1]而B[0..k/2-2]中的每个元素都 ≤B[k/2-2] B[k/2-1]。因此比A[k/2-1]小的元素最多有(k/2-1) (k/2-1) k-2个 →A[k/2-1]最多是第k-1小的元素不可能是第 k 小。边界处理数组越界用Math.min(index half, len) - 1确保不越界一个数组为空直接返回另一个数组的第 k 个元素k1返回两个数组当前首元素的最小值。方法二详解划分思想目标找到i和j使得i j (m n 1) / 2左半部分长度nums1[i-1] nums2[j]且nums2[j-1] nums1[i]为什么交换数组确保m n使得j (mn1)/2 - i 0时间复杂度从O(log(mn))优化到O(log min(m,n))。边界处理i0→nums1左半为空 →nums1LeftMax -∞im→nums1右半为空 →nums1RightMin ∞同理处理j0和jn六、时间复杂度和空间复杂度分析方法时间复杂度空间复杂度说明方法一O(log(mn))O(1)每次排除k/2个元素k 初始为(mn)/2方法二O(log min(m,n))O(1)在较短数组上二分每次排除一半✅ 两种方法均满足题目要求方法二更优。七、问题解答常见疑问Q1为什么方法一中k要减去(newIndex - index 1)因为排除了index到newIndex包含共(newIndex - index 1)个元素这些元素都小于第 k 小的元素所以新的第 k 小元素在剩余元素中是第k - count小的。Q2方法二中为什么j (m n 1) / 2 - i总长度L m n左半部分长度应为(L 1) / 2向上取整因为i j (L 1) / 2→j (L 1) / 2 - iQ3能否用归并排序的思想可以但时间复杂度O(mn)不符合要求。仅适用于不要求O(log n)的场景。Q4为什么方法二要找“最大的 i”满足nums1[i-1] nums2[j]因为我们要确保左半部分尽可能大从而右半部分尽可能小这样才能正确计算中位数。最大的i对应最优划分。八、优化思路优化1提前终止微优化在方法一中若一个数组已遍历完可直接返回结果无需继续循环。优化2位运算加速不推荐mid (left right) 1可防溢出但本题数据范围小无需。优化3模板化工程实践将getKthElement封装为通用工具函数支持任意 k 值publicstaticintfindKthSmallest(int[]A,int[]B,intk){// 实现...}九、数据结构与算法基础知识点回顾1. 中位数的数学性质将集合划分为两个等长或差1的子集左子集最大值 ≤ 右子集最小值。2. 二分查找的高级应用标准二分查找目标值第 k 小元素通过排除法缩小搜索空间划分问题通过性质判断调整搜索方向。3. 边界处理技巧用Integer.MIN_VALUE和Integer.MAX_VALUE处理空区间用Math.min防止数组越界。4. 复杂度分析log(mn)vslog min(m,n)后者更优尤其当一个数组很小时。十、面试官提问环节模拟对话面试官你的方法一中为什么比较nums1[k/2-1]和nums2[k/2-1]✅回答因为这两个位置之前的元素各有k/2-1个总共k-2个。较小值最多是第k-1小的元素所以可以安全排除它及其前面的所有元素。面试官方法二的时间复杂度为什么是O(log min(m,n))✅回答因为我们总是在较短的数组上进行二分查找搜索空间大小为min(m,n)每次迭代将空间减半所以是O(log min(m,n))。面试官如果允许重复元素算法还有效吗✅回答有效。因为我们的比较逻辑已经处理了相等情况重复元素不会影响排除逻辑。面试官能否推广到找第 k 小的元素k 任意✅回答方法一本身就是为找第 k 小设计的。方法二需要调整划分条件但核心思想仍适用。十一、这道算法题在实际开发中的应用1. 分布式数据库的跨分片查询数据按范围分片存储在不同节点查询中位数时需在多个有序分片中高效定位避免全量拉取。2. 流数据统计实时数据流分成多个有序缓冲区动态计算中位数用于异常检测或指标监控。3. 多源数据融合来自不同传感器的数据已分别排序快速计算整体中位数用于决策系统。4. 大数据 Top-K 查询在 MapReduce 中各 reducer 输出有序列表最终合并时需高效找到全局中位数。5. 金融风控系统不同渠道的交易金额已排序实时计算中位数用于风险评分。十二、相关题目推荐题号题目难度关联点4. 寻找两个正序数组的中位数困难本题33. 搜索旋转排序数组中等二分变种34. 在排序数组中查找元素的第一个和最后一个位置中等二分边界74. 搜索二维矩阵中等二维二分215. 数组中的第K个最大元素中等快速选择378. 有序矩阵中第 K 小的元素中等二分答案 学习路径建议34 → 33 → 4 → 378十三、总结与延伸核心思想总结问题转化中位数 → 第 k 小元素排除法每次排除k/2个不可能的元素划分思想通过数学性质直接定位中位数边界处理用极值和越界检查确保鲁棒性。延伸思考如果数组未排序→ 需先排序时间复杂度至少O((mn) log(mn))。如果内存受限→ 方法一更优因为它不需要额外空间且可流式处理。能否并行化→ 方法二的二分过程难以并行但方法一的排除步骤可部分并行。工程建议在生产代码中优先选择方法一更易理解和维护在面试中先实现方法一再尝试方法二展示深度始终写测试用例覆盖空数组、单元素、奇偶长度等情况。结语“寻找两个正序数组的中位数”是一道集数学洞察、算法技巧和工程实现于一体的经典难题。它不仅考察你对二分查找的掌握更检验你在面对复杂约束时的问题转化能力。正如计算机科学家 Niklaus Wirth 所言“算法 数据结构 程序。” 本题正是这一公式的完美体现——通过精巧的算法设计在不改变数据结构的前提下实现了理论最优的时间复杂度。✨练习建议手写两种方法确保理解每行逻辑尝试修改为找第 k 小的元素k 任意思考如何处理重复元素虽然本题已支持。掌握这道题你就掌握了在“有序世界”中高效统计的算法精髓。