题目描述:
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
分析解答
这个题目是LeetCode上的hard
题目,我的想法很简单,找出所有情况,可以提前结束循环的,就立即退出。
大概有以下几种:
- len1==0,len2!=0
- len1!=0,len2==0
- len1+len2为奇数
- len1+len2为偶数
代码实现:
package hard;
import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;
/**
* 寻找两个有序数组的中位数
*/ public class H4 {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 =nums2.length;
int len3 = len1+len2;
int[] nums3 = new int[len3]; //新数组
if (len1==0) return len2%2==0 ? (nums2[len2/2-1]+nums2[len2/2])/2.0 : nums2[len2/2];
if (len2==0) return len1%2==0 ? (nums1[len1/2-1]+nums1[len1/2])/2.0 : nums1[len1/2];
int i=0,j=0,k=0;
if (len3 %2 ==0){
while (i < len1 || j < len2){
if (i==len1) {
nums3[k] = nums2[j];
j++;
}else if (j==len2){
nums3[k] = nums1[i];
i++;
}else if (nums1[i]< nums2[j]){
nums3[k] = nums1[i];
i++;
}else {
nums3[k] = nums2[j];
j++;
}
if (k == len3/2) return (nums3[k]+nums3[k-1]) / 2.0;
k++;
}
}else {
while (i<len1 || j<len2){
if (i==len1){
nums3[k] = nums2[j];
j++;
}else if (j==len2){
nums3[k] = nums1[i];
i++;
}else if (nums1[i]< nums2[j]){
nums3[k] = nums1[i];
i++;
}else {
nums3[k] = nums2[j];
j++;
}
if (k == len3/2) return nums3[k];
k++;
}
}
return 0;
}
public static void main(String[] args) {
int[] nums2 = {1,3};
int[] nums1 = {2};
double out = findMedianSortedArrays(nums1,nums2);
System.out.println(out);
}
}
结果
执行结果:
通过
显示详情
执行用时 :3 ms, 在所有 Java 提交中击败了99.53% 的用户
内存消耗 :47.4 MB, 在所有 Java 提交中击败了93.06%的用户
阅读次数: 本文累计被阅读 1000000 次