logo标签列表

计算通过删除一个元素使序列排序的方法数

algorithmsorting
5

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

我们想通过删除其中一个元素来使数组按非递减顺序排序。我们可以有多少种方法做到这一点？

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

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

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

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

输入有什么限制？ - zenwraight
如果数组已经是非递减顺序，那该怎么办？ - zenwraight
只是一个想法。如果您说“仅删除一个项目”，那么对于一个不是非递减顺序的数组，答案是否会超过2呢？ - nice_dev
@zenwraight 我认为第三个输入展示了“如果数组已经是非递减顺序的情况”，此时答案将是数组元素的数量。 - SALEH
3个回答
5
你提供的示例已经涵盖了大部分情况；答案始终是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代码片段：
```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>");

2
这里是Java的解决方案。
基本上，您需要维护两个数组： 1. endHere数组，其中包含一个布尔值，指示以该索引结尾的数组是否已排序 2. startHere数组，其中包含一个布尔值，指示从该索引开始的数组是否已排序
一旦构建了这些数组，如果endingHere [i-1]和startHere [i + 1]为true且arr [i-1] <= arr [i + 1]，则可以删除索引处的数字，并且数组仍将保持排序。
public static int noOfWays(int[] arr) {
        int count = 0;
        if (arr != null) {
            if (arr.length != 1) {
                boolean[] startHere = new boolean[arr.length];
                boolean[] endHere = new boolean[arr.length];
                endHere[0] = true;
                startHere[arr.length - 1] = true;
                int j = arr.length - 2;
                for (int i = 1; i < arr.length; i++) {
                    endHere[i] = endHere[i - 1] & (arr[i - 1] <= arr[i]);
                    startHere[j] = startHere[j + 1] & (arr[j] <= arr[j + 1]);
                    j--;
                }
                for (int i = 0; i < arr.length; i++) {
                    boolean leftSorted = true;
                    boolean rightSorted = true;
                    if (i - 1 >= 0)
                        leftSorted = endHere[i - 1];
                    if (i + 1 < arr.length)
                        rightSorted = startHere[i + 1];
                    if (leftSorted && rightSorted) {
                        if (i - 1 >= 0 && i + 1 < arr.length) {
                            if (arr[i - 1] <= arr[i + 1]) 
                                count++;
                        } else 
                            count++;
                    }
                }
            }
        }
        return count;
    }
0

我解决了一个类似的问题，它检查给定的整数列表是否可以通过仅删除一个元素而变为非递减。

bool almostIncreasingSequence(std::vector<int> sequence) {
int err = 0;
int loc = 0;
for(int i=0;i<sequence.size()-1;i++){
    if(sequence[i]>=sequence[i+1]){
        err++;
        loc = i;
    }
}
if(err>1) return false;
if(err==0) return true;

if(loc==0) return true;
else if(loc == sequence.size()-2) return true;

if(sequence[loc-1]<sequence[loc+1]) return true;
if(sequence[loc-1]==sequence[loc+1]){
    if(sequence[loc]<sequence[loc+2])
        return true;
}


return false;
}

我认为这会给你一个解决问题的整体思路。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接