部队网站源码,做seo网站不用域名,wordpress wp posts,网络信用贷款哪个好【题目描述】
#xff08;困难#xff09;给定两个大小分别为 m 和 n 的正序#xff08;从小到大#xff09;数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平…【题目描述】
困难给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
【解题代码】
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {int len1 nums1.length;int len2 nums2.length;// 采用归并比较算法因为只需要取中位数所以新建数组大小nums只需要nums1和nums2一半即可int len3 (len1 len2) / 2 1;int[] nums new int[len3];int i1 0, i2 0, j 0;// 采用归并比较算法向数组nums按大小依次从nums1和nums2拷贝数据// 一直到nums1和nums2其中之一遍历完毕或者新建数组已经塞满while (true) {if (i1 len1 || i2 len2 || j len3) break;if (nums1[i1] nums2[i2]) {nums[j] nums1[i1];} else {nums[j] nums2[i2];}}// 如果新建数组还未塞满则从未遍历完的数组中直接拷贝数据把新建数组塞满 if (j len3) {if (i1 len1) System.arraycopy(nums1, i1, nums, j, len3 - j);if (i2 len2) System.arraycopy(nums2, i2, nums, j, len3 - j);}// nums1和nums2之和为偶数则返回中间两数之和的平均数 if (((len1 len2)) % 2 0) return (nums[len3 - 2] nums[len3 - 1]) / 2.0;// nums1和nums2之和为奇数则直接返回中间数 elsereturn nums[len3 - 1];
}
【解题步骤】
拿到题目可知此算法可以用归并算法进行处理因为只需要取中位数所以新建数组大小nums只需要nums1和nums2一半即可 nums2[i2]; int len1 nums1.length;int len2 nums2.length;// 采用归并比较算法因为只需要取中位数所以新建数组大小nums只需要nums1和nums2一半即可int len3 (len1 len2) / 2 1;int[] nums new int[len3]; 采用归并比较算法向数组nums按大小依次从nums1和nums2拷贝数据一直到nums1和nums2其中之一遍历完毕或者新建数组已经塞满 while (true) {if (i1 len1 || i2 len2 || j len3) break;if (nums1[i1] nums2[i2]) {nums[j] nums1[i1];} else {nums[j] nums2[i2];}
} 如果新建数组还未塞满则从未遍历完的数组中直接拷贝数据把新建数组塞满 if (j len3) {if (i1 len1) System.arraycopy(nums1, i1, nums, j, len3 - j);if (i2 len2) System.arraycopy(nums2, i2, nums, j, len3 - j);
} 根据nums1和nums2之和为奇数还是偶数返回相应的结果 // nums1和nums2之和为偶数则返回中间两数之和的平均数if (((len1 len2)) % 2 0)return (nums[len3 - 2] nums[len3 - 1]) / 2.0;
// nums1和nums2之和为奇数则直接返回中间数
elsereturn nums[len3 - 1];
【思路总结】
归并算法是数据结构排序算法中一个很重要的算法 归并排序非常稳定时间复杂度始终都是 N*logN另外除了常规的数组排序之外很多场景都可以应用到比如笔者以前做过的远程和本地文件夹同步算法就是两边文件名称数组进行归并比较处理大家要掌握这个算法思路以及应用技巧算法应用中要根据实际情况进行改良比如在这里因为是取中位数因此不需要向普通的场景申请两个数组之和的空间而只需要取一半即可
