Median of Two Sorted Arrays 解答
2024-09-15 07:20:40
Question
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Solution 1 -- Traverse Array
Use merge procedure of merge sort here. Keep track of count while comparing elements of two arrays. Note to consider odd / even situation.
Time complexity O(n), space cost O(1).
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length1 = nums1.length, length2 = nums2.length, total = length1 + length2;
int index1 = total / 2, index2;
// Consider two situations: (n + m) is odd, (n + m) is even
if (total % 2 == 0)
index2 = total / 2 - 1;
else
index2 = total / 2;
// Traverse once to get median
int p1 = 0, p2 = 0, p = -1, tmp, median1 = 0, median2 = 0;
while (p1 < length1 && p2 < length2) {
if (nums1[p1] < nums2[p2]) {
tmp = nums1[p1];
p1++;
} else {
tmp = nums2[p2];
p2++;
}
p++;
if (p == index1)
median1 = tmp;
if (p == index2)
median2 = tmp;
}
if (p < index1 || p < index2) {
while (p1 < length1) {
tmp = nums1[p1];
p1++;
p++;
if (p == index1)
median1 = tmp;
if (p == index2)
median2 = tmp;
}
while (p2 < length2) {
tmp = nums2[p2];
p2++;
p++;
if (p == index1)
median1 = tmp;
if (p == index2)
median2 = tmp;
}
}
return ((double)median1 + (double)median2) / 2;
}
}
Solution 2 -- Binary Search
General way to find Kth element in two sorted arrays. Time complexity O(log(n + m)).
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
if ((m + n) %2 == 1)
return findKthElement(nums1, nums2, (m + n) / 2, 0, m - 1, 0, n - 1);
else
return (findKthElement(nums1, nums2, (m + n) / 2, 0, m - 1, 0, n - 1) * 0.5 +
findKthElement(nums1, nums2, (m + n) / 2 - 1, 0, m - 1, 0, n - 1) * 0.5);
}
private double findKthElement(int[] A, int[] B, int k, int startA, int endA, int startB, int endB) {
int l1 = endA - startA + 1;
int l2 = endB - startB + 1;
if (l1 == 0)
return B[k + startB];
if (l2 == 0)
return A[k + startA];
if (k == 0)
return A[startA] > B[startB] ? B[startB] : A[startA];
int midA = k * l1 / (l1 + l2);
// Note here
int midB = k - midA - 1;
midA = midA + startA;
midB = midB + startB;
if (A[midA] < B[midB]) {
k = k - (midA - startA + 1);
endB = midB;
startA = midA + 1;
return findKthElement(A, B, k, startA, endA, startB, endB);
} else if (A[midA] > B[midB]) {
k = k - (midB - startB + 1);
endA = midA;
startB = midB + 1;
return findKthElement(A, B, k, startA, endA, startB, endB);
} else {
return A[midA];
}
}
}
最新文章
- Linux中不同主机建立免登陆
- Python之操作Redis、 RabbitMQ、SQLAlchemy、paramiko、mysql
- asp.net core 笔记
- Js 类定义的几种方式
- MySQL忘记root密码的找回方法
- MAC OS设置JDK小结
- ###《Max-Margin Early Event Detectors》
- V - 不容易系列之(4)――考新郎（第二季水）
- 5.4.2 RegExp实例方法
- 使用Cmder的几个问题
- HashSet集合
- 在SOUI中使用线性布局
- python自动化开发-[第十天]-线程、协程、socketserver
- Python随手记—各种方法的使用
- 一起学Hadoop——TotalOrderPartitioner类实现全局排序
- HIVE metastore Duplicate key name 'PCS_STATS_IDX' (state=42000,code=1061)
- python mysql redis mongodb selneium requests二次封装为什么大都是使用类的原因，一点见解
- [dpdk][kernel][driver] 如何让DPDK的UIO开机自动加载到正确的网卡上
- java项目中异常处理情况
- pthon自动化之路-编写登录接口