本文主要是介绍【打卡第190道】【数组】【leetCode高频】:4. 寻找两个正序数组的中位数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1、题目描述
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
2、算法分析
题目中说的是有序的两个数组nums1,nums2,求这两个数组的中位数。
基本思路:
①只存在一个数组,需要判断数组长度的奇偶数
②两个数组都存在,对数组进行排序,然后取中间数。
本题比较简单吧。
3、代码实现
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int nums1Length = nums1.length;int nums2Length = nums2.length;int resLength = nums1Length + nums2Length;int[] res = new int[resLength];// 其中的一个数组长度为0的情况if(nums1Length == 0){// 判断num2的奇偶数if(nums2Length % 2 == 0){double c = (nums2[nums2Length / 2 - 1] + nums2[nums2Length / 2]) / 2.0;return c;}else{double d = nums2[nums2Length / 2];return d;}}if(nums2Length == 0){// 判断num1的奇偶数if(nums1Length % 2 == 0){double x = (nums1[nums1Length / 2 - 1] + nums1[nums1Length / 2]) / 2.0;return x;}else{double y = nums1[nums1Length / 2];return y;}}// 两个数组都存在,先进行排序成一个数组int count = 0;int i = 0,j = 0;while(count != resLength){// 两个数组的长度不相等if(nums1[i] > nums2[j]){res[count++] = nums2[j++];}else {// 反正后面也比较res[count++] = nums1[i++];}// 其中一个数字长度大于另一个数组的长度if(i == nums1Length){while(j != nums2Length){res[count++] = nums2[j++];} }if(j == nums2Length){while(i != nums1Length){res[count++] = nums1[i++];}}}if(count % 2 == 0){return (res[count / 2 - 1] + res[count / 2]) / 2.0;}else{return res[count / 2];}}
}
这篇关于【打卡第190道】【数组】【leetCode高频】:4. 寻找两个正序数组的中位数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!