力扣4题：寻找两个正序数组的中位数

本文主要是介绍力扣4题：寻找两个正序数组的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目描述】

（困难）给定两个大小分别为 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，另外除了常规的数组排序之外，很多场景都可以应用到，比如笔者以前做过的远程和本地文件夹同步算法，就是两边文件名称数组，进行归并比较处理，大家要掌握这个算法思路以及应用技巧；
算法应用中，要根据实际情况进行改良，比如在这里因为是取中位数，因此不需要向普通的场景申请两个数组之和的空间，而只需要取一半即可

这篇关于力扣4题：寻找两个正序数组的中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！