『1』合并两个正序数组
我的想法:
先借鉴归并排序的关键步骤将两个数组合并,然后根据数组长度是奇数还是偶数返回中位数。
实现代码:
class Solution {
// Using the Key Thinking of Merge Sort
// M is the length of nums1, N is the length of nums2
// Time Complexity: O(M + N)
// Space COmplexity: O(M + N)
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
int[] nums = new int[m + n];
if (m == 0) {
if (n % 2 == 0) return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
else return nums2[n / 2];
}
if (n == 0) {
if (m % 2 == 0) return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
else return nums1[m / 2];
}
int count = 0;
int i = 0, j = 0;
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) nums[count++] = nums1[i++];
else nums[count++] = nums2[j++];
}
while (i < m) nums[count++] = nums1[i++];
while (j < n) nums[count++] = nums2[j++];
if (count % 2 == 0) return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
else return nums[count / 2];
}
}