algorithm - 通过删除一项来计算使序列排序的方法数

Question

我最近遇到了一个基本上是以下问题的变体的问题：

我们希望通过从中删除一项来使数组按非降序排序。我们有多少种方法可以做到这一点？

例如，如果输入数组是[3, 4, 5, 4]，则答案将为 2，因为我们可以删除其中一个5或第二个4。

如果数组是[3, 4, 5, 2]答案1，我们可以删除2。

如果数组是[1, 2, 3, 4, 5]答案5，我们可以删除任何一个元素。

我正在努力解决这个问题。任何有关解决方案策略的指针/方向都将受到高度赞赏。

标签： algorithmsorting

Answer 1

您提供的示例已经涵盖了大多数情况；答案总是 0、1、2 或 N，您应该能够通过对序列进行一次迭代来找到解决方案。

从左到右遍历数组，寻找左侧大于右侧的相邻元素对。

如果你在序列的末尾没有找到一个递减的对，那么这个序列已经是非递减的，答案是 N。

如果找到一个递减对，检查删除左边的元素是否有效，即它之前的元素是否不大于右边的元素，然后检查删除右边的元素是否有效，即左边的元素是否不大于该元素在正确的元素之后。

如果这些选项都不起作用，您可以返回答案 0，因为不可能使序列不递减；例如 [2,2,1,1]。

如果选项中的 1 或 2 个有效，请继续检查序列的其余部分；如果您找到另一个递减对，则答案变为 0（不可能）。

在伪代码中：

options = 0
for i is 1 to array.length - 1
    if array[i-1] > array[i]
        if options is not 0
            return 0
        if i is 1 or array[i-2] <= array[i]
            ++options
        if i is array.length - 1 or array[i-1] <= array[i+1]
            ++options
        if options is 0
            return 0
if options is 0
    options = array.length
return options

或者翻译成一个简单的 Javascript 代码片段：

function numberOfWays(array) {
    var options = 0
    for (var i = 1; i < array.length; i++) {
        if (array[i-1] > array[i]) {
            if (options != 0) return 0;
            if (i == 1 || array[i-2] <= array[i]) ++options;
            if (i == array.length - 1 || array[i-1] <= array[i+1]) ++options;
            if (options == 0) return 0;
        }
    }
    return (options == 0) ? array.length : options;
}

var arrays = [[1,2,3,4],[1,3,2,4],[1,2,4,3],[1,3,4,2],[2,4,1,3],[2,2,1,1]];
for (var a in arrays)
    document.write(arrays[a] + " &rarr; " + numberOfWays(arrays[a]) + "<br>");