title: 算法小练——寻找两个有序数组的中位数
date: 2019-11-29 19:00:11
categories:

• Algorithms
  tags:
• hard

寻找两个有序数组的中位数

描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

代码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] arr = new int[nums1.length+nums2.length];
        int i =0,j=0;
        int k=0;
        while(i<nums1.length && j<nums2.length) {
        	if(nums1[i]<nums2[j]) {
        		arr[k++] = nums1[i++];
        	}else {
        		arr[k++] = nums2[j++];
        	}
        }
        if(i==nums1.length && k!=arr.length) {
        	while(j<nums2.length) {
        		arr[k++] = nums2[j++];
        	}
        }
        if(j==nums2.length&& k!=arr.length) {
        	while(i<nums1.length) {
        		arr[k++] = nums1[i++];
        	}
        }
        if(arr.length%2==0) {
        	return (arr[arr.length/2]+arr[arr.length/2-1])/2.0;
        }else {
        	return arr[arr.length/2];
        }
    }
}

笔记

思路就是，将两个数组有序合并，然后根据数组长度，判断中位数是某个数，还是某两个数相加