增加序列C++

Question

我尝试解决CodeFights上的这个挑战，但它不起作用。我最好的解决方案得到了25/26（最后一次测试超出了时间限制），但我删除了，因为我昨天试过了（这是O（n^2））。现在我尝试了一个新的O（n）。我非常疲倦，我很想今天完成这个任务，所以请帮助我。

下面是语句： 给定一个整数序列作为数组，确定是否可以通过从数组中删除不多于一个元素来获得严格增加的序列。

例

For sequence = [1, 3, 2, 1], the output should be 
almostIncreasingSequence(sequence) = false; 

There is no one element in this array that can be removed in order to get a strictly increasing sequence. 

For sequence = [1, 3, 2], the output should be 
almostIncreasingSequence(sequence) = true. 

You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3]. 

这里是我的代码，到现在为止......（可怜的代码）：

#include <iostream> 
#include <vector> 

#include <algorithm> 

bool almostIncreasingSequence(std::vector<int> sequence) 
{ 
    int count = 0; 


    for(int i = 0; i < sequence.size()-1; i++) 
    { 
     if(sequence[i] > sequence[i+1]) 
     { 
      count++; 
      sequence.erase(sequence.begin(), sequence.begin() + i); 
      i--; 
     } 
     if(count == 2) 
      return false; 
    } 
    return true; 
} 

int main() 
{ 
    std::cout << std::endl; 
    return 0; 
} 

Answer 1

这里是一个C++ 11溶液O（N）运行时：

constexpr auto Max = std::numeric_limits<std::size_t>::max(); 
bool is_sorted_but_skip(const std::vector<int>& vec, std::size_t index = Max){ 
    auto Start = index == 0 ? 1 : 0; 
    auto prev = vec[Start]; 
    for(std::size_t i = Start + 1; i < vec.size(); i++){ 
     if(i == index) continue; 
     if(prev >= vec[i]) return false; 
     prev = vec[i]; 
    } 
    return true; 
} 

bool almostIncreasingSequence(std::vector<int> v) 
{ 
    auto iter = std::adjacent_find(v.begin(), v.end(), [](int L, int R){ return L >= R; }); 
    if(is_sorted_but_skip(v, std::distance(v.begin(), iter))) 
     return true; 
    return is_sorted_but_skip(v, std::distance(v.begin(), std::next(iter))); 
} 

我们使用std::adjacent_find找到的第一个元素，比iter大于或等于它的下一个元素。然后我们检查序列是否严格排序，同时跳过iter的位置。

否则，我们检查，虽然我们跳过iter+1的位置

更糟糕的情况下，复杂的顺序是严格分类：3的线性扫描

Demo

Answer 2

这仍然是O（N^2），因为你删除的第一要素在每次迭代中的向量。不要删除循环中的第一个元素，也不要删除i--。

如果你必须删除数字（你不，但仍然），至少从列表的末尾做它。这种方式擦除一个数字是可能 O（1）操作（我不是100％确定这是如何执行std :: vector）。

你真的不需要擦除数字。

Answer 3

这里有一个提示（当然，几乎解决方案真的）：

如果您看到一个元素与下一个元素之间的减少，那么您必须删除其中的一个元素（*）。

现在，如果在两个不相交的元素对之间找到两个减少值？这是正确的:-)

记住这一点，你应该能够解决你的问题，使用线性扫描和一些恒定时间的工作。

_{（*）不包括第一对和最后一对元素。}