java取两个数址键的中位数
时间: 2024-01-23 11:08:08 浏览: 19
可以使用以下代码来获取两个整数的中位数:
```java
public static int getMedian(int a, int b) {
return (a + b) / 2;
}
```
这个方法将两个整数相加,然后除以2来获取它们的中位数。请注意,这个方法只适用于整数。如果你想要获取两个浮点数的中位数,你需要使用不同的算法。
相关问题
Java寻找两个有序数组的中位数
题目描述:
给定两个大小为 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
解题思路:
题目要求时间复杂度为 O(log(m+n)),很明显是要用到二分查找的思想。
首先,我们需要确定中位数的位置。对于两个长度分别为 m 和 n 的有序数组,它们的中位数位置为 (m+n+1)/2 和 (m+n+2)/2,因为当 m+n 为奇数时,这两个位置的值是相同的;当 m+n 为偶数时,这两个位置的值分别为中间两个数。
然后,我们需要在两个数组中分别找到第 k/2 个数(k 为中位数位置),比较它们的大小,如果 nums1[k/2-1] < nums2[k/2-1],则说明中位数位于 nums1 的右半部分和 nums2 的左半部分之间,此时可以舍弃 nums1 的左半部分,将 k 减去 nums1 的左半部分的长度,继续在 nums1 的右半部分和 nums2 的左半部分中寻找第 k/2 个数;反之,如果 nums1[k/2-1] >= nums2[k/2-1],则说明中位数位于 nums1 的左半部分和 nums2 的右半部分之间,此时可以舍弃 nums2 的左半部分,将 k 减去 nums2 的左半部分的长度,继续在 nums1 的左半部分和 nums2 的右半部分中寻找第 k/2 个数。
当 k=1 时,中位数为两个数组中的最小值。
Java代码实现:
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int k = (m + n + 1) / 2;
double median = findKth(nums1, 0, m - 1, nums2, 0, n - 1, k);
if ((m + n) % 2 == 0) {
int k2 = k + 1;
double median2 = findKth(nums1, 0, m - 1, nums2, 0, n - 1, k2);
median = (median + median2) / 2;
}
return median;
}
private double findKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int 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));
}
}
}
Java两个有序数组的中位数
题目描述:
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2,请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
解题思路:
1. 将两个数组合并成一个数组,再对合并后的数组进行排序,找到中位数
时间复杂度为O(m+n)log(m+n),不符合题目要求
2. 利用二分法查找
首先,我们可以理解中位数的定义:如果某个有序数组的长度是奇数,那么其中位数就是最中间那个元素,如果是偶数,那么就是最中间两个元素的平均值。
在本题中,我们需要找到两个有序数组 A 和 B 的中位数,我们可以考虑从中位数的定义入手。如果我们能够将两个数组分别分成两部分,并且使得左半部分和右半部分分别满足以下两个条件:
1.左半部分的所有元素都小于右半部分的所有元素。
2.左半部分和右半部分分别包含了 A 和 B 数组的一半元素。
那么中位数就可以通过以下公式得到:
median = max(left_part) (len(A) + len(B) 为偶数)
median = (max(left_part) + min(right_part))/2 (len(A) + len(B) 为奇数)
为了使得划分满足上述两个条件,我们可以对较短的那个数组进行二分查找,然后根据查找到的位置将两个数组进行划分,最后再根据上述公式计算中位数。
具体实现见代码。
Java代码:
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
//确保nums1比nums2短
if (m > n) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
int tmp = m;
m = n;
n = tmp;
}
int iMin = 0, iMax = m;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = (m + n + 1) / 2 - i;
if (i < iMax && nums2[j - 1] > nums1[i]) {
iMin = i + 1;
} else if (i > iMin && nums1[i - 1] > nums2[j]) {
iMax = i - 1;
} else {
int maxLeft = 0;
if (i == 0) {
maxLeft = nums2[j - 1];
} else if (j == 0) {
maxLeft = nums1[i - 1];
} else {
maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
}
if ((m + n) % 2 == 1) {
return maxLeft;
}
int minRight = 0;
if (i == m) {
minRight = nums2[j];
} else if (j == n) {
minRight = nums1[i];
} else {
minRight = Math.min(nums1[i], nums2[j]);
}
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)