JavaScript中二次函数的大O时间效率

Question

我试图提高功能的效率。它目前是二次的，我想把它变成对数。

当前函数的倒数第三行也让我感到困惑，我想澄清一下。

function solution(arr){
   let result = 0
    for ( let i = 0; i < arr.length; i++)
        for (let j = 0; j < arr.length; j++)
            if (arr[i] == arr[j])
                result = Math.max(result, Math.abs(i - j));
         return result;
 }

我该如何解决这个问题？

Answer 1

至少，您可以更改循环的索引并省略自检并再次检查相同的对。

function solution(arr){
    let result = 0
    for (let i = 0; i < arr.length - 1; i++)
        for (let j = i; j < arr.length; j++)
            if (arr[i] === arr[j])
                result = Math.max(result, Math.abs(i - j));
    return result;
}

最短的方法是O（n），通过采用哈希表来存储值的第一个找到的索引。

function solution(array) {
    var hash = {};
    return array.reduce(
        (m, v, i) => Math.max(m, i - (hash[v] = v in hash ? hash[v] : i)),
        0
    );
}

var array = [1, 3, 4, 5, 1, 3, 4, 5, 6, 2, 3];

console.log(solution(array));

Answer 2

在上面的函数中，目标是从数组中找到最大数。现在是result = Math.max(result, Math.abs(i - j));的第三行到最后一行的含义，我将其分为两部分来解释，

首先，Math.abs(i-j)将被执行并提供i和j之间差异的绝对值。

在此之后，将调用外部函数Math.max()方法，它将为您提供从第一步获得的result和absolute value之间的最大值。现在最大值将存储在result中。这就是函数的工作方式。

现在这个语句是基于条件的，这意味着它只会在arr[i]==arr[j]时执行。

我希望它清除了该计划的工作流程。