我一上来没读清题，想着这题这么简单，直接就上手写了：
package leetcode.day_12_05;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class FindMedianSortedArrays0004 {
public List<Integer> listOf(int[] array) {
List<Integer> result = new ArrayList<>();
for (int i : array) {
result.add(i);
}
return result;
}
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
double middle = 0.0;
List<Integer> l1 = listOf(nums1);
List<Integer> l2 = listOf(nums2);
l2.addAll(l1);
l2.sort(Comparator.comparingInt(a -> a));
if (l2.size() % 2 == 0) {
middle = ((double) l2.get(l2.size() / 2) + (double) l2.get(l2.size() / 2 - 1)) / 2;
} else {
middle = (double) l2.get(l2.size() / 2);
}
return middle;
}
}
虽然是通过了，但是在我又看一遍题目之后，才发现难点所在。
本题要求时间复杂度控制在O(log(m+n)),而我使用了排序算法就肯定不行了。
因为Arrays.sort时间复杂度是O(nlogn)，光是这就超了。
于是我又想出第二种法：
package leetcode.day_12_05;
public class FindMedianSortedArrays0004_02 {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int l1 = nums1.length;
int l2 = nums2.length;
int[] num = new int[l1 + l2];
int i = 0;
int j = 0;
int n = 0;
while (i < l1 && j < l2) {
if (nums1[i] < nums2[j]) {
num[n] = nums1[i++];
} else {
num[n] = nums2[j++];
}
n++;
}
if (i < l1) {
for (int a = i; a < l1; a++) {
num[n++] = nums1[a];
}
} else {
for (int a = j; a < l2; a++) {
num[n++] = nums2[a];
}
}
if (num.length % 2 == 0) {
return ((double) num[num.length / 2] + (double) num[num.length / 2 - 1]) / 2;
} else {
return num[num.length / 2];
}
}
public static void main(String[] args) {
int[] nums1 = {1, 3};
int[] nums2 = {2, 5};
System.out.println(new FindMedianSortedArrays0004_02().findMedianSortedArrays(nums1, nums2));
}
}
相比于第一种虽然是快了不少，但是时间复杂度还是不够，这次的是O(m+n)。目前这能在先这样了。
欢迎评论区大神指点。
Original: https://www.cnblogs.com/soberw/p/15876461.html
Author: soberw-
Title: Leetcode随缘刷题之寻找两个正序数组的中位数
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/579956/
转载文章受原作者版权保护。转载请注明原作者出处！