两个有序数组的中位数用java实现
时间: 2023-09-30 07:07:28 浏览: 53
以下是用 Java 实现求两个有序数组的中位数的代码:
```java
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length, len2 = nums2.length;
int len = len1 + len2;
if (len % 2 == 1) {
return findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, len / 2 + 1);
} else {
return (findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, len / 2) + findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, len / 2 + 1)) / 2.0;
}
}
private int findKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1, len2 = end2 - start2 + 1;
if (len1 > len2) {
return findKth(nums2, start2, end2, nums1, start1, end1, k);
}
if (len1 == 0) {
return nums2[start2 + k - 1];
}
if (k == 1) {
return Math.min(nums1[start1], nums2[start2]);
}
int i = start1 + Math.min(len1, k / 2) - 1;
int j = start2 + Math.min(len2, k / 2) - 1;
if (nums1[i] > nums2[j]) {
return findKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
} else {
return findKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
}
```
其中,`findKth()` 方法实现了求两个有序数组的第 k 小数的功能,`findMedianSortedArrays()` 方法则根据数组长度的奇偶性来决定求中位数的方式。时间复杂度为 O(log(m+n)),其中 m 和 n 分别为两个有序数组的长度。
相关推荐
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)