arrays - 一次仅删除一个元素后，查找从父数组产生的已排序数组的数量

Question

暴力方法是一次一个一个地删除每个数字，并检查结果数组是否已排序并维护此类排序数组的计数。这将花费 O(n^2) 时间。

是否有另一种方法可以在小于 O(n^2) 的时间内找到计数？

注意:一次只删除一个元素后，只需要查找此类排序数组的计数。

例如:

输入:[1 2 3 4 5 4]

输出:2 ([1 2 3 4 4 ], [1 2 3 4 5])

输入:[1 2 3 4 2]

输出:1 ([1 2 3 4])

Answer 1

我相信我的时间复杂度为 O(n) - 该算法仅执行一次列表遍历，检查每个元素一次。

<小时/>

对于每个元素:

• 如果下一个元素大于或等于当前元素，则继续。
• 如果下一个元素小于当前元素...
  • (设置一个失败位。如果该位已经设置，则停止检查。)
  • 如果该元素前面两个索引的元素相对于该元素进行排序，则意味着我们可以省略下一个元素，但仍然可以排序。添加匹配项。
  • 如果该元素后面的第一个元素索引相对于该元素前面的第一个元素索引进行排序，则意味着我们可以省略当前元素并且仍然可以排序。添加匹配项。

<小时/>

一旦运行完成，代码就会检查失败位。

• 如果未设置失败位，则所有内容均已排序，并且可能列表的数量等于列表中元素的数量。
• 如果设置了失败位，则存在一个未排序的元素。已记录比赛次数。
• 如果设置了失败位并且循环提前退出，则至少有两个未排序的元素 - 不可能匹配。

<小时/>

EXAMPLE - steps are in reverse order

STEP  1 3 4 6 5 7 8
7                 ^ 8<=(end), pass
6               ^ 7<=8, pass
5             ^ 5<=7, pass
4b          ^   ^ 6<=7, we can safely omit next element (5) - add match
4a        ^   ^ 4<=5, we can safely omit current element (6) - add match
4           ^ 6!<=5, set failure bit
3         ^ 4<=6, pass
2       ^ 3<=4, pass
1     ^ 1<=3, pass

<小时/>

下面是cpp中的实现。请注意，向量被填充以避免第一个或最后一个元素的额外边界检查逻辑。

#include <iostream>
#include <vector>
#include <climits>

int main(void) {

  std::vector<int> invals;
  int temp = 0;

  //pad the vector to get around out-of-bounds checking
  invals.push_back(INT_MIN);
  invals.push_back(INT_MIN);

  //get user input
  std::cout << "enter vals, ctrl_d to calculate" << std::endl;

  while(std::cin >> temp) { invals.push_back(temp); }

  //padding
  invals.push_back(INT_MAX);
  invals.push_back(INT_MAX);

  int matches = 0;
  int fail = 0;
  for(int i = 2; i < invals.size() - 2; i++) {
    //sorted - continue
    if(invals[i] <= invals[i+1]) { continue; }

    //something was unsorted
    else {

      //there was already another unsorted element - this list cannot
      //be sorted by removing just 1 element. break and fail
      if(fail == 1) { fail = 2; break; }

      else {
        //set fail bit
        fail = 1;

        //check if the next element can be removed
        if(invals[i] <= invals[i+2]) { matches++; }

        //check if this element can be removed
        if(invals[i-1] <= invals[i+1]) { matches++; }
      }
    }
  }

  std::cout << "\n\nmatches: ";
  if(fail == 0) { std::cout << invals.size() - 4 << std::endl; }
  else if(fail == 1) { std::cout << matches << std::endl; }
  else if(fail == 2) { std::cout << 0 << std::endl; }

  return(0);

}

Demo