电子商城网站建设公司,二级建造师考试报名官网,硬件开发工程师薪资,wordpress调用数据库连接文章目录题目描述思路 代码题目描述
算是拖了好久的题目 #xff0c;一开始刷的时候没打算直接冲困难不过面试常客了#xff0c;还是得冲掉#xff0c;而且不能留下心魔嘛#xff01;难点在于实现时间复杂度 O(log(m n))#xff0c;显而易见得用二分法
思路 代码题目描述
算是拖了好久的题目 一开始刷的时候没打算直接冲困难不过面试常客了还是得冲掉而且不能留下心魔嘛难点在于实现时间复杂度 O(log(m n))显而易见得用二分法
思路 代码
长度奇偶情况处理因为偶数要取平均值所以这边进行了两次函数调用分别取较小、较大的中位数再取平均奇数就相当于跑重复了一次主要思路基于二分法的基础上进行排除法两数组元素都够的情况每次舍去 k / 2 个数一方不够的情况直接指向数组尾看对比情况舍保证空数组一定是 nums1[ ]证明 更多见代码注释注意k 并非下标
class Solution {/*** 正确性证明每次去掉的值都是应当去掉的* 因为答案一定不在数组n去掉范围中极端情况下也是在数组m范围的尾部* 核心排除法不断去掉可去值并维护k(中位数为第k小数)* ps其实有效代码只有 20 行 */public double findMedianSortedArrays(int[] nums1, int[] nums2) {int n nums1.length;int m nums2.length;// 1 2k 不是下标比如 k 1指第一个也就是 index k - 1// left right 是为了奇偶// 奇数情况 left right// 偶数情况 left right - 1int left (n m 1) / 2;int right (n m 2) / 2;// 奇数情况两次一样的过程// 偶数情况中间俩个值的平均值return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) / 2.0;}int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k){int len1 end1 - start1 1;int len2 end2 - start2 1;// 保证空数组一定是 nums1[]if(len1 len2){return getKth(nums2, start2, end2, nums1, start1, end1, k);}// 出现空数组直接化成求一数组第k小数的情况if(len1 0){return nums2[start2 k - 1];}// 找到最后的情况直接返回两数组当前最小值if(k 1){return Math.min(nums1[start1], nums2[start2]);}// 指向第k/2小的位置 or 指向尾部int i start1 Math.min(len1, k / 2) - 1;int j start2 Math.min(len2, k / 2) - 1;// 舍去值的数量不一定相等指向尾部情况// 舍nums2的情况if(nums1[i] nums2[j]){return getKth(nums1, start1, end1, nums2, j 1, end2, k - (j - start2 1));}// 舍nums1的情况else{return getKth(nums1, i 1, end1, nums2, start2, end2, k - (i - start1 1));}}}无注释版
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int mid1 (nums1.length nums2.length 1) / 2;int mid2 (nums1.length nums2.length 2) / 2;return (getMid(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, mid1) getMid(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, mid2)) / 2.0;}public int getMid(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {int len1 end1 - start1 1;int len2 end2 - start2 1;if(len2 len1) {return getMid(nums2, start2, end2, nums1, start1, end1, k);}if(len1 0) {return nums2[start2 k - 1];}if(k 1) {return Math.min(nums1[start1], nums2[start2]);}int index1 start1 Math.min(len1, k / 2) - 1;int index2 start2 Math.min(len2, k / 2) - 1;if(nums1[index1] nums2[index2]) {return getMid(nums1, index1 1, end1, nums2, start2, end2, k - (index1 - start1 1));}else {return getMid(nums1, start1, end1, nums2, index2 1, end2, k - (index2 - start2 1));}}
}
