LeetCode 4 题解
给定两个大小为 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
解题：思路是：归并之后，取中间值
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int len = nums1.length + nums2.length; int[] a = new int[len]; int k = 0; for (int i = 0; i < nums1.length; i++) { a[k++] = nums1[i]; } for (int i = 0; i < nums2.length; i++) { a[k++] = nums2[i]; } mergesort(a, 0, len - 1); if (len % 2 == 1) { return (double) a[len / 2]; } else { return (double) (a[len / 2 - 1] + a[len / 2]) / 2; } } /** * @param a * @param i * @param length */ private void mergesort(int[] a, int start, int end) { if (end > start) { int mid = (start + end) / 2; mergesort(a, start, mid); mergesort(a, mid + 1, end); merge(a, start, mid, end); } } /** * @param a * @param start * @param i * @param end */ private void merge(int[] a, int start, int mid, int end) { // 二分 start -mid 是一个，mid -end 是一个 int[] b = new int[end + 1]; int k = start; int i, j; for (i = start, j = mid + 1; i <= mid && j <= end; k++) { if (a[i] < a[j]) { b[k] = a[i++]; } else { b[k] = a[j++]; } } while (j <= end) { b[k++] = a[j++]; } while (i <= mid) { b[k++] = a[i++]; } for (int l = start; l <= end; l++) { a[start++] = b[l]; } } }
