关注
给定两个有序数组arr1和arr2,两个数组长度都为N,求两个数组中所有数的上中位数。
例如:
arr1 = {1,2,3,4};
arr2 = {3,4,5,6};
一共8个数则上中位数是第4个数,所以返回3。
arr1 = {0,1,2};
arr2 = {3,4,5};
一共6个数则上中位数是第3个数,所以返回2。
要求:时间复杂度O(logN)
public static int getUpMedian(int[] arr1, int[] arr2) {
if (arr1 == null || arr2 == null || arr1.length != arr2.length) {
throw new RuntimeException("Your arr is invalid!");
}
return findProcess(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1);
}
public static int findProcess(int[] arr1, int start1, int end1, int[] arr2,
int start2, int end2) {
if (start1 == end1) {
return Math.min(arr1[start1], arr2[start2]);
}
// 元素个数为奇数,则offset为0;元素个数为偶数,则offset为1;
int offset = ((end1 - start1 + 1) & 1) ^ 1;
int mid1 = (start1 + end1) / 2;
int mid2 = (start2 + end2) / 2;
if (arr1[mid1] > arr2[mid2]) {
return findProcess(arr1, start1, mid1, arr2, mid2 + offset, end2);
} else if (arr1[mid1] < arr2[mid2]) {
return findProcess(arr1, mid1 + offset, end1, arr2, start2, mid2);
} else {
return arr1[mid1];
}
}
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
转发
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
528788次浏览 9007人参与
# 晒一晒我的offer #
3046936次浏览 51630人参与
# 简历中的项目经历要怎么写 #
402197次浏览 6729人参与
# 在国企工作的人,躺平了吗? #
81364次浏览 1033人参与
# 如何写一份好简历 #
234846次浏览 3633人参与
# 你的简历改到第几版了 #
280822次浏览 4313人参与
# 我想象的工作vs实际工作 #
82586次浏览 1435人参与
# 春招你拿到offer了吗 #
339035次浏览 5067人参与
# 学历贬值真的很严重吗? #
5742次浏览 74人参与
# 你已经投递多少份简历了 #
268361次浏览 4141人参与
# 我的实习日记 #
397904次浏览 7240人参与
# 联想求职进展汇总 #
48227次浏览 687人参与
# 百度工作体验 #
21152次浏览 225人参与
# 找工作时遇到的神仙HR #
164397次浏览 1682人参与
# 机械人,你的秋招第一份简历被谁挂了 #
28929次浏览 518人参与
# 最后再改一次简历 #
775477次浏览 11021人参与
# 如何判断面试是否凉了 #
909931次浏览 13974人参与
# 实习,投递多份简历没人回复怎么办 #
902628次浏览 16089人参与
# 浅聊一下我实习的辛苦费 #
75100次浏览 697人参与
# 我发现了面试通关密码 #
299657次浏览 5728人参与