20191016：（leetcode习题）寻找两个有序数组的中位数

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

• 题目
• 大致思路
• 代码实现

题目

1. 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
2. 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
3. 你可以假设 nums1 和 nums2 不会同时为空。

大致思路

先合并两个数组，再排序，最后根据长度为奇数或偶数来计算中位数即可。
           

代码实现

package com.immunize.leetcode.findMedianSortedArrays;

import java.util.Arrays;

/**
 * 获取两个有序数组的中位数
 * 
 * @author Mr IMMUNIZE
 *
 */
public class Solution {
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int[] a = new int[nums1.length + nums2.length];
		int sum = nums1.length + nums2.length;

		double mid = 0.0d;
		for (int i = 0; i < nums1.length; i++) {
			a[i] = nums1[i];
		}
		for (int i = 0; i < nums2.length; i++) {
			a[nums1.length + i] = nums2[i];
		}
		Arrays.sort(a);

		mid = sum % 2 == 1 ? (double) a[sum / 2] : (a[sum / 2 - 1] + a[sum / 2]) / 2;
		return mid;
	}
}