求职 求两个有序数组的中位数

我问问 for 求职面试圈 · August 17, 2018 · Last by 陈子昂 replied at October 07, 2019 · 1603 hits

求两个有序数组的中位数,最优

共收到 2 条回复 时间 点赞

二路归并改一下,时间复杂度O(n),空间复杂度O(1)

public static int middle(int[] a, int[] b) {
int middleIndex = (a.length + b.length + 1) / 2 - 1;
if (middleIndex == 0) {
return -1;
}
int tmp;
int i = 0, j = 0, k = 0;
for (; i < a.length && j < b.length; ++k) {
if (a[i] < b[j]) {
tmp = a[i++];
} else {
tmp = b[j++];
}
if (k == middleIndex) {
return tmp;
}
}
if (i < a.length) {
return a[middleIndex - k + i];
}
return b[middleIndex - k + j];
}
def middleList(l1: list, l2: list) -> tuple:
return l1[int(len(l1) / 2)], l2[int(len(l2) / 2)]


l1 = [1, 2, 3, 8, 7, 4, 5, 6]
l2 = [1, 2, 31, 2, 3, 7, 1, 0, 4, 5, 4, 4, 5]
print(middleList(l1, l2))

List本身有序啊,是这样吗。。

需要 Sign In 后方可回复, 如果你还没有账号请点击这里 Sign Up