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

我问问 for 求职面试圈 · 2018年08月17日 · 最后由 陈子昂 回复于 2019年10月07日 · 293 次阅读

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

共收到 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 本身有序啊,是这样吗。。

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册