javascript - 从数字数组中删除一个数字以对数组进行排序

Question

我们有一个数字数组，我们需要找到可以删除数组中一个数字的方法总数，如果删除该数字，则会对数组进行排序。

例如，如果我们有 [3,4,5,4]，我们应该返回 2，因为如果我们删除 5 或第二个 4，我们的数组将被排序。

但是如果我们得到类似 [4,5,2,3,4] 的结果，我们应该返回 0，因为删除它们中的任何一个都不会对数组进行排序。

我相信这与 Longest increasing subsequence 有关

如果我错了请纠正我，但这应该是这样工作的:

我们应该找到最长的递增子序列并删除不在该子序列中的所有内容。

考虑到这一点，我使用了这样的函数来查找 LIS:

function findSubsequence(arr){
var allSubsequence = [],
    longestSubsequence = null,
    longestSubsequenceLength = -1;

for(var i=0;i<arr.length;i++){          //i=1
    var subsequenceForCurrent = [arr[i]],
        current = arr[i],
        lastElementAdded = -1;
    for(var j=i;j<arr.length;j++){
        var subsequent = arr[j];
        if((subsequent > current) && (lastElementAdded<subsequent)){
            subsequenceForCurrent.push(subsequent);
            lastElementAdded = subsequent;
        }
    }
    allSubsequence.push(subsequenceForCurrent);
}
for(var i in allSubsequence){
    var subs = allSubsequence[i];
    if(subs.length>longestSubsequenceLength){
        longestSubsequenceLength = subs.length;
        longestSubsequence = subs;
    }
}
return longestSubsequence;
}


(function driver(){
    var sample = [87,88,91, 10, 22, 9,92, 94, 33, 21, 50, 41, 60, 80];
    console.log(findSubsequence(sample));
})();

但这给了我最高的数字，我不确定我应该如何删除其中一个以保持数组排序并找到所有可能的方法。

有什么想法吗？

Answer 1

这种方法似乎有点复杂。我认为使用蛮力方法会更清晰并且占用更少的资源:对于数组中的每个项目，尝试删除它，然后检查数组是否已排序。但是不要使用 sort 来检查它是否已排序(具有 O(N log N) 复杂性)，而是检查数组中的每个项目是否是与前一个相同或大于 (O(N)):

const checkSorted = arr => arr.every((num, i, arr) => i === 0 || num >= arr[i - 1]);
const checkRemovalCount = arr => arr.reduce((countSoFar, _, i, arr) => {
  const removedArr = [...arr.slice(0, i), ...arr.slice(i + 1)];
  return countSoFar + checkSorted(removedArr);
}, 0);
console.log(checkRemovalCount([3,4,5,4]));
console.log(checkRemovalCount([4,5,2,3,4]));
console.log(checkRemovalCount([87,88,91, 10, 22, 9,92, 94, 33, 21, 50, 41, 60, 80]));