美文网首页算法学习/计算机基础/面试题
算法:获取数组的一个分界点,使得左右两边和相等

算法:获取数组的一个分界点,使得左右两边和相等

作者: 喵子G | 来源:发表于2019-04-30 16:10 被阅读0次

要求给定一个数组,获取数组的一个分界点的下标,使得该分界点的两侧子数组的和相等。如果存在多个分界点,只返回第一个分界点的下标,如果没有则返回-1。
要求:时间复杂度不得超过O(n)。

测试用例:

输入:[-20, 30, 10, 40, 20]
返回:3

分析:正常的计算思路应该是,用一个index标记当前计算的下标,从数组第二个元素(即index为1开始)开始计算,将这个元素左边的相加求和,然后右边相加求和,对比是否相等。然后index++依次遍历,知道index 遍历到数组倒数第二个元素,都没有找到则返回-1。

Java实现

按照上面的思路,最直接的算法为:

    static int middleIndexWithArray(Integer[] array) {
        if (array.length < 3) return -1;
        for (int i = 1; i < array.length - 1; i++) {
            int leftSum = 0;
            int rightSum = 0;
            for (int j = 0; j < i; j++) {
                leftSum += array[j];
            }
            for (int k = i + 1; k < array.length; k++) {
                rightSum += array[k];
            }
            if (leftSum == rightSum) {
                return i;
            }
        }
        return - 1;
    }

复杂度分析:
首先最外层参数为 i 的for循环遍历取决于数组数据大小,数组长度为n则最大需要 n - 2 次运算。
外层for循环内部的两个for循环的 j + k 最大循环次数实际等于 n - 1。
所以最终:(n - 2)(n - 1) 复杂度为O(n^2),不符合算法要求。

那么我们需要优化的就是如何降低复杂度,先思考,为什么会出现这么高的时间复杂度。大多数做计算对比的算法复杂度过高都是因为做了重复性的运算,我们看一下之前的算法并模拟一下计算的过程
先模拟一下leftSum的计算:
当i == 1 时,leftSum += array[0]
当i == 2时,leftSum += array[0]、leftSum += array[1]
当i == 3时,leftSum += array[0]、leftSum += array[1]、leftSum += array[2]
在看一下rightSum的计算:
当i == 1 时,rightSum += array[2]、rightSum += array[3]、rightSum += array[4]
当i == 2时,rightSum += array[3]、rightSum += array[4]
当i == 3时,rightSum += array[4]
是不是发现问题了,实际上最外层的for循环内部计算 leftSum和rightSum进行了大量的重复计算,当i == 3时,leftSum还是将数组的第0、1、2元素累加,但是之前i==2时,数组的第0、1元素已经做过一次加法了,那么第一步加法就是多余的,rightSum的计算同理。

既然发现了问题所在,就是怎么优化掉重复的加法问题了。现在换一种思维方式:
开始需要比较的是array数组下标为1的元素,这时如果知道了整个数组的和为allSum。那么左边子数组的和leftSum就是array的第一个元素array[0]。右边的子数组的和就是rightSum = allSum - leftSum - array[1];
当下一次index2时,将上一次计算的leftSum用于下一次比较,leftSum只需要再加上array[1],就是左边数组的和,而右边的子数组的和还可以通过rightSum = allSum - leftSum - array[1]计算。
这样的话,左侧数组和只需要每次累加一个新的需要对比的元素,右侧直接就可以通过减法计算不需要累加:

    static int middleIndexWithArray(Integer[] array) {
        if (array.length < 3) return -1;
        int allSum = 0;
        int leftSum = 0;
        int rightSum = 0;
        for (int i = 0; i < array.length; i++) {
            allSum += array[i];
        }
        for (int i = 1; i < array.length - 1; i++) {
            leftSum += array[i - 1].intValue();
            rightSum = allSum - leftSum - array[i].intValue();
            if (leftSum == rightSum) return i;
        }
        return -1;
    }

复杂度分析:第一个for循环计算allSum取决于数组容量n,后面for循环计算最多需要计算 n - 2 次,最多需要 2n - 2,时间复杂度为 O(n)。

使用包含20万条长度数据的数组,测试优化后前后时间对比:

        TimeTool.check("Midde", new Task() {
            public void execute() {
                Integer[] array = new Integer[200001];
                for (int i = 0; i < 200001; i++) {
                    if (i < 100000) {
                        array[i] = i;
                    } else if (i == 100000) {
                        array[i] = -1;
                    } else {
                        array[i] = 200000 - i;
                    }
                }
                System.out.println(middleIndexWithArray(array));
            }
        });

优化前

【Midde】
开始:16:08:22.262
100000
结束:16:08:34.178
耗时:11.916秒
-------------------------------------

优化后

【Midde】
开始:16:10:12.414
100000
结束:16:10:12.425
耗时:0.01秒
-------------------------------------

Objective-C实现

NSInteger middleIndexWithArray(NSArray<NSNumber *> * array) {
    if (array.count < 3) return -1;
    NSInteger leftSum = 0;
    NSInteger rightSum = 0;
    NSInteger allSum = 0;
    // n
    for (NSNumber *sum in array) allSum += sum.integerValue;
    // max: n - 2
    for (NSInteger i = 1; i < array.count - 1; i++) {
        leftSum += array[i - 1].integerValue;
        rightSum = allSum - leftSum - array[i].integerValue;
        if (leftSum == rightSum) return i;
    }
    // 复杂度 2n - 2 => O(n)
    return -1;
}

总结

这个算法题主要就是考察思维逻辑的,并没有对数据结构的知识进行深入考察,即便不清楚数组查找的复杂度为O(1),也不会出现错误,只需要灵活思考就能够解决,属于简单的问题。

相关文章

  • 算法:获取数组的一个分界点,使得左右两边和相等

    要求给定一个数组,获取数组的一个分界点的下标,使得该分界点的两侧子数组的和相等。如果存在多个分界点,只返回第一个分...

  • 左右两边子数组的和相等

    前缀和

  • 两个算法的swift实现

    在某iOS群里群主发了几个面试题,我很感兴趣,就尝试一下。 题目:给定一个数组,请获取一个数组的分界点,使得该分界...

  • Object类详解

    相等性的比较: (1)对于原生数据类型来说,比较左右两边的值是否相等。 (2)对于原生数据类型来说,比较左右两边的...

  • 6月10日读书笔记

    1.===运算符不会对左右两边的值进行类型转换,所以左右两边值是否相等比较明确,==运算符当两边值类型不等时(相等...

  • 前端算法面试题整理

    1.统计字符串出现最多的字母及其次数 2.排序算法 3去重算法 4.判断位置数组是否相等 首先判断两个数组是否相等...

  • 算法 | 顺序查找

    【算法思想】 按照数组元素的先后次序,从第一个元素开始遍历,逐个检验是否和查找的数据相等。 【算法实例】 在包含1...

  • 任意数分三组,使得每组的和尽量相等

    题目:任意数分三组,使得每组的和尽量相等思路:第一次遇到这个题目的时候,那叫一个难字,对于算法题,算法本身可能并没...

  • 面试题 16.21. 交换和

    给定两个整数数组,请交换一对数值(每个数组中取一个数值),使得两个数组所有元素的和相等。 返回一个数组,第一个元素...

  • 剑指 Offer II 012. 左右两边子数组的和相等

    根据题目描述。。 左右两边和相等。。所以求出总的和 符合条件的下标条件就是2 * sum == total - ...

网友评论

    本文标题:算法:获取数组的一个分界点,使得左右两边和相等

    本文链接:https://www.haomeiwen.com/subject/kfjvnqtx.html