时间戳

首页 > 解决方案 > TapeEquilibrium，两个边缘案例失败的解决方案

java - TapeEquilibrium，两个边缘案例失败的解决方案

问题描述

目前正在处理来自实践的代码问题，由于某种原因，我无法获得超过 83% 的总体正确率，最初我以 100% 的正确率解决了它，但时间复杂度为 N^2（它需要为 N 或更低）

我已经调整了我的代码以能够在 O(N) 中解决，但现在我的正确性已经下降到 77%，我目前正在尝试解决 2 个元素的情况，即）[1000,-1000] 应该返回 2000，但我返回一个 0；

链接到关于 Codility 的问题：https ://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

问题：

给定一个由 N 个整数组成的非空数组 A。数组 A 代表磁带上的数字。

任何整数 P，例如 0 < P < N，都会将此磁带分成两个非空部分：A[0]、A[1]、...、A[P - 1] 和 A[P]、A[ P + 1], ..., A[N - 1]。

两部分的差值是：|(A[0] + A[1] + ... + A[P - 1]) - (A[P] + A[P + 1] + .. . + A[N - 1])|

换句话说，它是第一部分的总和与第二部分的总和之间的绝对差。

为以下假设编写一个有效的算法：

N 是 [2..100,000] 范围内的整数；数组 A 的每个元素都是 [−1,000..1,000] 范围内的整数

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int pval = Integer.MAX_VALUE;
        int sum = 0;
        int pone = 0;
        int ptwo = 0;
        int currdiff = 0;
        for(int i = 0; i<A.length; i++ ){
            sum += A[i];
        }
        
        ptwo = sum;
        for(int j = 0; j< A.length; j++){
            pone += A[j];
            ptwo -= A[j];
            currdiff = Math.abs(ptwo - pone);
            if(currdiff < pval)
                pval = currdiff;
        }
        return pval;
    }
}

标签： javatime-complexity

解决方案

任何整数 P，例如 0 < P < N，将这个磁带分成两个非空部分

“非空”在这里至关重要。如果您尝试在第二个循环中打印这两个部分，您会看到在最后一次迭代中第二部分是空的。

您需要做的就是跳过循环中的最后一次迭代：

public int solution(int[] A) {
    int pval = Integer.MAX_VALUE;
    int sum = 0;
    int pone = 0;
    int ptwo = 0;
    int currdiff = 0;
    for(int i = 0; i<A.length; i++ ){
        sum += A[i];
    }
    
    ptwo = sum;
    for(int j = 0; j< A.length-1; j++){ //<- notice -1 here
        pone += A[j];
        ptwo -= A[j];
        currdiff = Math.abs(ptwo - pone);
        if(currdiff < pval)
            pval = currdiff;
    }
    return pval;
}

推荐阅读