代码之家 › 专栏 › 技术社区 › Emad Dehnavi

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

sorting arrays javascript

Emad Dehnavi · 技术社区 · 8 年前

我们有一个数字数组,我们需要找到在数组中删除一个数字的方法总数,如果删除这个数字,将对数组进行排序。

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

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

我相信这和 Longest increasing subsequence

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

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));
})();

但这给了我最高的数字,我不知道我应该如何删除其中一个保持数组排序和找到所有可能的方法。

知道吗?

2 回复 | 直到 8 年前

CertainPerformance 8 年前

这种方法似乎有点复杂。我想会更清楚和使用暴力方法减少资源负担:对于数组中的每个项,尝试删除它,然后检查数组是否在之后排序。但不要用 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]));

-2

Vasim Shaikh 8 年前

您可以使用数学库删除最高的数字。

<!DOCTYPE html>
<html>
<head>
    <title></title>
</head>
<body>
    <script type="text/javascript">
var sample = [87,88,91, 10, 22, 9,92, 94, 33, 21, 50, 41, 60, 80];
sample.sort(function(a, b){return a - b});
list = remove_highest(sample)

console.log(list) // [9, 10, 21, 22, 33, 41, 50, 60, 80, 87, 88, 91, 92]

function remove_highest(list) {
    return list.filter(function(n) { return n != Math.max.apply( Math, list ) })
}       
    </script>

</body>
</html>