javascript - 优化函数以减少对数组的迭代

Question

作为 CodeSignal 挑战的一部分，我被要求:

Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

For sequence = [1, 3, 2, 1], the output should be function(sequence) = false. There is no one element in this array that can be removed in order to get a strictly increasing sequence.

For sequence = [1, 3, 2], the output should be function(sequence) =
true. You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

Guaranteed constraints: 2 ≤ sequence.length ≤ 105 & -105 ≤ sequence[i] ≤ 105.

我的代码可以工作，但我正在寻找性能更高的解决方案，因为挑战已修复 4 秒的执行时间限制。

这是我的代码:

const almostIncreasingSequence = seq => {
  let i = 0;
  while (i < seq.length) {
    const filtred = [...seq];
    // splice 1 element at index i from array
    filtred.splice(i, 1);
    // create a `sorted` array with only unique numbers and sort it
    const sorted = [...new Set([...filtred].sort((a, b) => a - b))];
    if (filtred.join("") === sorted.join("")) {
      console.log(`filtred [${filtred}] ✅  sorted [${sorted}]`);
      return true;
    } else {
      console.log(`filtred [${filtred}] 🛑  sorted [${sorted}]`);
    }
    i++;
  }
  return false;
};

// array of random numbers for testing
const testArr = Array.from({ length: 100000 }, () =>
  Math.floor(Math.random() * 100)
);
// [1,,N] for testing 
// const testArr = Array.apply(null, { length: 100001 }).map(Number.call, Number);

console.log(almostIncreasingSequence(testArr));

Answer 1

您可以获取找到的索引。

This approach tests either three consecutive elements, like

            v
1   2  [3   8   4]  5   6   7   -> found at index 3

or takes for the next loop a check which omits the found value by checking the found index.

                v
1   2   3  [8   4   5]  6   7
            ^ omit value on found index

Then if not in sequence, the adjacent items are checked to prevent this pattern

            v
1   2   3   1   2   5   6   7
        3   >   2

            v
1   2   3   8   2   5   6   7
        3   >   2

and if found, more than one element is in wrong position.

function inSequence(array) {
    var i,
        found;
        
    for (i = 1; i < array.length - 1; i++) {
        if ((found === i - 1 || array[i - 1] < array[i]) && array[i] < array[i + 1]) continue;
        if (array[i - 1] >= array[i + 1] || found !== undefined) return false;
        found = i;
    }
    return true;
}

console.log(inSequence([2, 1]));
console.log(inSequence([1, 2, 3]));
console.log(inSequence([2, 1, 3]));
console.log(inSequence([1, 2, 4, 3]));
console.log(inSequence([1, 2, 3, 8, 4, 5, 6, 7]));
console.log(inSequence([1, 2, 3, 8, 4, 5, 6, 9, 7]));
console.log(inSequence([2, 1, 3, 4, 5, 2]));
console.log(inSequence([1, 2, 3, 1, 2, 5, 6, 7]));
console.log(inSequence([1, 2, 3, 8, 2, 5, 6, 7]));

.as-console-wrapper { max-height: 100% !important; top: 0; }