简化计算每个元素与其右侧元素之间的差值

Question

我能让它变得更简单吗？

 for(int k=0;k<n;k++)
 for(int l=(k+1);l<n;l++)
 {
     tot+=(max(a[k],a[l])-min(a[k],a[l]));
 }

此程序当前执行时间较长，超过了时间限制。

Answer 1

下面是一个稍微简单一点的版本：

var k = -1,
    l, tot

while(++k < n){
  l = k
  while(++l < n){
    tot += Math.abs(a[k] - a[l])
  }
}

使用es6语法也可以非常简洁地获得相同的功能，尽管我不确定哪个版本在性能方面更快。下面是一个同时包含这两种方法的fiddle。

"use strict";
var a = [3, 22, 12, 99, 1, 6, 19];
var test = a.reduce((previousValue, currentValue, currentIndex, array) => {
  return previousValue + a.reduce((pv, cv, ci, arr) => {
    return ci > currentIndex ? pv + Math.abs(cv - currentValue) : pv
  }, 0)
}, 0)
console.log(test)

Answer 2

在我看来，您正在尝试计算每个元素与其右侧所有元素之间的差值。你可以做的是计算整个数组的和，然后每次你从一个元素移动到下一个元素时，从总数中减去这个特定的数字，总差值现在就是总和-当前元素。

// Sort the array 'a' first and then run this.
int sum = calculateSum() // Write this method yourself to find total
for (int i = 0; i < n; i++)
{
    sum -= a[i];
    tot += (sum - a[i] * (n - i + 1));
}

最后一行通过考虑理想情况下减去所考虑的元素的次数，从总和中减去总差。