1

昨晚我在看 Codility 上的演示 Equi 任务，并在以下功能上得分 12/100：

function solution(A) {
    var n = A.length;
    var p = 0;
    var sum = 0;
    var sumLeft = 0;
    var sumRight = 0;
    var equilExists = 0;

    if (n == 0) {
        return -1;
    }

    for (i=0; i<=n; i++) {
        sum = A[i];
        for (j=0; j<=n; j++) {
        if (j < i) {
            sumLeft += A[j];
        } else if (j > i) {
            sumRight += A[j];
        }
        if (sumLeft == sumRight) {
            equilExists = 1;
            p = i;
            return p;
                }
        }
    }

    if (equilExists == 0) {
        return -1;
    }
}

对于那些不熟悉该任务的人，可以在http://blog.codility.com/2011/03/solutions-for-task-equi.html找到它

我想知道是否有人可以帮助指出我的解决方案在哪里失败？

非常感谢！

4

11 回答 11

1

您的解决方案的最大问题是嵌套循环。

您在每个索引处迭代整个数组以计算当前索引处左右部分的总和。他们的要求之一是 O(n) 复杂性，而您的要求是 O(n^2)（我认为）。

您只需要在数组上循环两次：一次获得元素的总和，一次找到平衡。在第二个循环开始时，左侧的总和 == 0，右侧的总和 == 总计。遍历元素，您只需要更新总和：右总和 = 总 - 左总和 - 当前索引处的值，然后比较右 == 左，如果不是 - 左总和按当前索引处的值增长。

这一篇我得了100分：

function solution(A) {
  var total = (function(a){ var l = a.length, s = 0; while(--l>-1){ s+=a[l] } return s; }(A)), 
  eq = -1, 
  l = A.length, 
  Lsum = 0, 
  Rsum = 0; 
  A.forEach(function(n,i){ 
    Rsum = total - Lsum - n; 
    if(Rsum == Lsum){ eq = i; /* in fact no need to continue, should terminate here. */ } 
    Lsum += n; 
  }); 
  return eq;
}
于 2013-09-26T13:29:46.663 回答
0

首先，您的函数总是返回 0（如果 n>0）。这是因为您将if (sumLeft == sumRight)内部 for 循环放在了内部。
如果你解决了这个问题，你仍然会遇到问题，因为变量sumLeft并sumRight没有在内部 for 循环之前初始化。如果你解决了这些问题，这个函数至少是正确的，它得到了 75 分。但是，您的算法显然是二次的。为了解决这个问题，你必须问自己当你加一时左右和如何变化i。是否有必要从头开始重新计算？

于 2013-08-24T21:49:07.670 回答
0

您的解决方案失败主要是因为它始终只能检测到处于平衡状态的第一个索引。

例如，如果有一个序列在索引 3 和 6 处都具有平衡，但如果我们将您的解决方案应用于该序列，那么它将始终只返回 3，并且永远不会提供 6 作为答案。

这是因为您没有在任何地方存储已经发现处于平衡状态并领先于它们的指数。您需要使用递归或为已经发现处于平衡状态的索引维护一些存储，并相应地修改您的解决方案以捕获所有此类索引，而不仅仅是第一个。

此外，几乎没有定义但从未在您的答案中使用的变量，例如 sum 变量，从而导致不必要的开销。

于 2013-08-12T05:55:32.933 回答
0 
class Solution {
public int solution(int[] A) {
    if(A.length < 1) {
        return -1;
    }
    double leftSum = 0, sum = 0;
    for(int i=0; i<A.length; i++) {
        sum += A[i];
    }
    for(int i=0; i<A.length; i++) {
        if(leftSum == sum - leftSum - A[i]) {
            return i;   
        }
        leftSum += A[i];
    }
    return -1;
}

}

于 2014-10-08T00:00:52.867 回答
0

我用这个解决方案得分 100%，它是用 C++ 编写的，但你会看到算法。我要做的第一件事是创建一个数组运行和的向量，然后我使用它首先检查边缘情况，然后循环整个数组以获得第一个 equi 索引。复杂度将始终为 O(n)。

#include <vector>

using namespace std;

long long Sum(vector<int>::const_iterator begin, vector<int>::const_iterator end, vector<long long>& sums)
{
    long long sum = 0;
    for(vector<int>::const_iterator it = begin; it != end; it++)
    {
        sum += (long long) (*it);
        sums.push_back(sum);
    }
    return sum;
}

int solution(vector<int> &A)
{
    vector<long long> sums;

    long long allSum = Sum(A.begin(), A.end(), sums);

    int N = sums.size();

    if(N==0)
        return -1;

    if(N==1 && allSum == 0)
        return 0;

    if(N > 1)
    {
        if(sums[N-2] == 0)
            return N-1;
    }

    if((allSum- sums[0]) == 0)
        return 0;

    long long prefixSum = 0;
    for(int i = 1; i < N; ++i)
    {
        prefixSum = sums[i-1];

        if(prefixSum == 0 && i == N-1)
            return i;

        if(prefixSum == (allSum - sums[i]))
            return i;
    }

    return -1;
}
于 2013-09-04T09:45:21.160 回答
0 
\\ Javascript solution
function solution(A) {
    const sortAry = A.sort((a, b) => a - b);
    var initVal = 1;
    for (let i = 0; i < sortAry.length; i++) {
        if (sortAry[i] <= 0) continue;
        if (sortAry[i] < initVal) continue;
        if (sortAry[i] === initVal) {
            initVal += 1;
        } else {
            return initVal;
        }
    }
    return initVal;
}
于 2020-05-16T23:11:58.103 回答
0

一个略有不同的（100分）：

function solution(list) {
  var length = list.length,
      sumRight,
      sumLeft = 0,
      equi_index = -1;

  if (length === 0) {
    return equi_index;
  } else if (length === 1) {
    return 0;
  }

  var total = (function(){
    var sum = 0;
    while (length--) {
      sum += list[length];
    }
    return sum;
  })();

  list.some(function(each, index){
    sumRight = total - sumLeft - each;
    if (sumLeft === sumRight) {
      equi_index = index;
      return true; // stop iteration
    }

    sumLeft += each;
  });

  return equi_index;
}
于 2016-05-20T21:31:09.813 回答
0

JS 解决方案得分 - 100% 并且执行得非常快

function solution(A) {
   const values = new Set(A) // dedupe array
   let i = 0
   while(++i) { // iterate from 1, the first possible positive integer greater than 0 
       if(!values.has(i)) { // check if set has value and break loop if it does not
           break
       }
   }
   return i
}
于 2021-02-27T04:05:35.847 回答
0

我的答案是这个：

function balance(arr){

var N = arr.length;
if (N == 0){ return -1};

var suma = 0;
for (var i=0; i<N; i++){
    suma += arr[i];
}

var suma_iz = 0;
for(i=0; i<N; i++){
    var suma_de = suma - suma_iz - arr[i];
    if (suma_iz == suma_de){
        return i};
    suma_iz += arr[i];
}

  return -1;}

该解决方案满足 O(n) 要求

于 2016-02-27T11:38:42.390 回答
0

我不敢相信这里的一些答案有多长；也许我只是想不同..？

也许自从创建这个线程以来测试已经改变了..？

function solution(A) {
  for (i=1;i<100000;i++)
    if (!A.includes(i)) return A;
}

我看到了另一种类似的解决方案，但感觉不需要重复数据删除。编辑：转换为 Set/hash 和 dedup 实际上获得了 100% 的性能，而我的却没有。诡异的！

编辑：所以我做了一些基准测试。我的解决方案是任何具有较小值的数组都快一个数量级。对于具有较大内部值的数组，Set 解决方案更快。

Array length: 400000 of random values up to 40000
Call to MySolution took 5218.896612003446 milliseconds
Call to NotMySolution took 226.6879480034113 milliseconds
Array length: 600000 of random values up to 1000
Call to MySolution took 40.543023988604546 milliseconds
Call to NotMySolution took 204.18921500444412 milliseconds

这确实表明，至少 NodeJS 可以更有效且可预测地处理集合。有趣的结果。虽然我不应该感到惊讶，更多内存密集型解决方案可能会更快。尽管从技术上讲，缺少一项测试；实际测试表明返回值不应超过 100,000，但是，数组的任何值都可以达到 1,000,000 .. 因此 Set() 解决方案实际上应该失败，但由于某种原因错过了这个测试..？

2行代码。实际上，我通常可能会用三元组将它写在一行中，但你不能在 tern 中使用 return，你可以返回一个 tern 但在循环中，这将返回第一次迭代。从技术上讲，无论如何都可能是其中之一。

编辑：最后我没有注意到实际的评估。显然可以有更多的性能方法，这并没有获得完整的性能分数，但实际上，特别是对于 JS，我们并不是在每个 CPU 周期之后，我认为可读性和可维护性似乎并不重要。

于 2022-01-11T04:06:12.443 回答
0

我的 JavaScript 解决方案...

 function solution(A) {

    var length = A.length;

    // special case to void total calculation
    if(!length) return -1;

    var lSum = 0;
    var rSum = 0;
    var i    = 0;

    // get total
    for(; i < length; rSum += A[i++]);

    // reset iterator
    i = 0;

    for(; i < length; i++) {
        rSum -= A[i];
        if(rSum === lSum) return i;
        lSum += A[i];        
    }

    return -1;
}
于 2016-01-05T20:53:49.183 回答