LeetCode4. 寻找两个有序数组的中位数(java)
题目:
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例:
代码:
- 解法一
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
//判断两个数组中若有一个数组为空
if(nums1==null&&nums2==null) {
return 0;
}
//创建一个新数组 长度为两个数组之和
int[] nums = new int[nums1.length + nums2.length];
//原数组元素遍历到新数组中
for (int i = 0; i < nums1.length; i++) {
nums[i] = nums1[i];
}
for (int i = 0; i < nums2.length; i++) {
nums[nums1.length + i] = nums2[i];
}
//对数组进行排序
Arrays.sort(nums);
//判断数组个数奇偶 找出中位数
if (nums.length % 2 == 0) {
return ((nums[nums.length / 2]) + (nums[nums.length / 2 - 1])) / 2.0;
} else {
return nums[nums.length / 2];
}
}
}
- 别人的代码
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int nums2length = nums2.length;
int[] r = new int[nums1.length + nums2length];
int index = 0;
int j = 0;
for (int num : nums1) {
while (j < nums2length && num > nums2[j]) {
r[index] = nums2[j];
j++;
index++;
}
r[index] = num;
index++;
}
for (; j < nums2length; j++) {
r[index] = nums2[j];
index++;
}
int mi = r.length / 2;
return r.length % 2 == 1 ? r[mi] : (r[mi - 1] + r[mi]) / 2.0;
}
}