新年混沌JavaScript，需要加速

Question

类似于这个问题但这是给Python的

黑客等级描述的原始问题

目前，我正在尝试迭代大量数组，并计算交换了多少次数字。

排序后的数组如下所示：[1,2,3,4,5]和一个数字只能两次交换到前面(倒数到0)。

如果一个数字超过2个无序，数组被认为“太混乱”，这个过程应该停止。

与其对泡沫进行分类，我只是简单地浏览并计算实际的掉期。由于实际上不需要排序数组，所以我的代码可以工作，但有几个测试会因为大数组而超时。

对于如何加快这一进程，有什么想法吗？

function minimumBribes(q) {
console.log(sort(q));

    function sort(items) {
     let bribes = 0;

     for (let i = 0; i < items.length; i++) {
         if (items[i] - (i + 1) > 2) return "Too chaotic";
         for (let j = 0; j < i; j++) {
             if (items[j] > items[i]) bribes++;
         }
     } 
     return bribes;
   }
}

Answer 1

减少内部循环迭代次数.

问题是，内部循环正在循环太多的项目。结果是你花费了太多的时间来处理你所知道的无关数据。

由于功能应该退出，如果它检测到一个位置已经超过2贿赂，你只需要让内环检查位置从你正在检查的项目2，而不是从线的开始。

快速解

它只需要稍微修改您的代码，但是由于您已经通过调用内部函数sort来使情况复杂化，所以示例刚刚删除了内部函数。

for (j = pos-2; j < i; j++) {行是改进的地方，pos是函数中的item[i]。

function minBribe(queue) {
    var bribes = 0, i, j;
    for (i = 0; i < queue.length; i++) {
        const pos = queue[i], at = i + 1;
        if (pos - at > 2) { return "Too chaotic" } 
        for (j = Math.max(0, pos - 2); j < i; j++) {
            if (queue[j] > pos) { bribes++ }
        }
    } 
    return bribes;
}

这使得解决方案从O(n^2)下降到接近O(n)，但是贿赂的数量是一个因素，所以它更接近O(n + (m^{0.5}/2))，m是贿赂的数量。(这只是一个近似)

Answer 2

你不需要比较任何两个元素。只需将数组值(粘贴)与数组的索引进行比较。请记住，贴纸是基于一的，指数是零的。

minimumBribes = q => {
    const bribes = q.reduce( (bribes, assigned, actual, too_chaotic) => { 
        const distance = assigned - 1 - actual
        if (distance>2) too_chaotic=true
        else return bribes + distance*(distance>0)
    }, 0);
    return isNaN(bribes) ? "Too chaotic" : bribes;
}

打破减少的伎俩是从这个信息丰富的帖子.

Answer 3

输入数组为：1 2 5 3 7 8 6 4，这表示：

• 5跃升2个位置，因此增量计数器2 (c = 2)
• 7跳2个位置，所以增量计数器2 (c = 4)
• 8跳2个位置，所以增量计数器2 (c = 6)
• 然后，6领先于4，但它在指数5，所以它必须跳出至少一个位置。因此，计数器应该是递增1 (c = 7)，但是减少方法中的逻辑没有捕捉到它，bc值大于它所在的索引。

还需要考虑额外的逻辑，以捕捉值向后推的边缘情况，但也需要考虑交换位置。