0

我试图解决顶部编码器上的锯齿形序列问题。我的代码的时间复杂度是 O(n*n)。如何将其减少到 O(n) 或 O(nlog (n)) 伪代码或算法解释对我真的很有帮助这是问题陈述。问题陈述

如果连续数字之间的差异在正负之间严格交替，则数字序列称为之字形序列。第一个差异（如果存在）可以是正面的也可以是负面的。少于两个元素的序列通常是锯齿形序列。

例如，1,7,4,9,2,5 是锯齿形序列，因为差值 (6,-3,5,-7,3) 交替出现正负。相反，1,4,7,2,5 和 1,7,4,5,5 不是之字形序列，第一个是因为它的前两个差是正数，第二个是因为它的最后一个差是零。

给定一个整数序列，sequence，返回序列的最长子序列的长度，即锯齿形序列。子序列是通过从原始序列中删除一些元素（可能为零）而获得的，而其余元素则保持其原始顺序。

这是我的代码

#include <iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;

class ZigZag
{
  public:
  int dp[200][2];
  void print(int n)
  {
      for(int i=0;i<n;i++)
      {
          cout<<dp[i][0]<<endl;
      }
  }
  int longestZigZag(vector<int> a)
  {
      int n=a.size();
      //int dp[n][2];
      for(int i=0;i<n;i++)
      {
          cout<<a[i]<<" "<<"\t";
      }
      cout<<endl;
      memset(dp,sizeof(dp),0);
      dp[0][1]=dp[0][0]=1;
      for(int i=1;i<n;i++)
      {
            dp[i][1]=dp[i][0]=1;

            for(int j=0;j<i;j++)
            {
                if(a[i]<a[j])
                {
                   dp[i][0]=max(dp[j][1]+1,dp[i][0]);
                }
               if(a[j]<a[i])
               {
                    dp[i][1]=max(dp[j][0]+1,dp[i][1]);
               }
            }
            cout<<dp[i][1]<<"\t"<<dp[i][0]<<" "<<i<<endl;
            //print(n);
      }
      cout<<dp[n-1][0]<<endl;
      return max(dp[n-1][0],dp[n-1][1]);
  }
};
4

5 回答 5

5

你可以使用贪婪的方法在O(n)中做到这一点。取第一个不重复的数字 - 这是您的之字形子序列的第一个数字。检查数组中的下一个数字是否小于或大于第一个数字。

案例1：如果lesser，检查下一个元素并继续直到找到最小元素（即）之后的元素将大于前一个元素。这将是你的第二个元素。

情况2：如果更大，检查下一个元素并继续直到找到最大元素（即）之后的元素将小于前一个元素。这将是你的第二个元素。

如果您使用案例 1 找到第二个元素，请使用案例 2 找到第三个元素，反之亦然。在这两种情况之间保持交替，直到原始序列中没有更多元素。你得到的结果数字将形成最长的锯齿形子序列。

例如：{ 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }

结果子序列：

1 -> 1,17（情况 2）-> 1,17,5（情况 1）-> 1,17,5,15（情况 2）-> 1,17,5,15,5（情况 1）- > 1,17,5,15,5,16 (案例 2) -> 1,17,5,15,5,16,8 (案例 1)

因此最长之字形子序列的长度为 7。

你可以参考 sjelkjd 的解决方案来实现这个想法。

于 2012-10-23T11:41:48.340 回答
1

由于子序列不一定是连续的，因此您不能使其成为 O(n)。在最坏的情况下，复杂度为 O(2^n)。但是，我做了一些检查以尽快切断子树。

int maxLenght;

void test(vector<int>& a, int sign, int last, int pos, int currentLenght) {
    if (maxLenght < currentLenght) maxLenght = currentLenght;
    if (pos >= a.size() || pos >= a.size() + currentLenght - maxLenght) return;
    if (last != a[pos] && (last - a[pos] >= 0) != sign) 
        test(a,!sign,a[pos],pos+1,currentLenght+1);
    test(a,sign,last,pos+1,currentLenght);
}

int longestZigZag(vector<int>& a) {
    maxLenght = 0;
    test(a,0,a[0],1,1);
    test(a,!0,a[0],1,1);
    return maxLenght;
}
于 2012-10-14T10:28:08.407 回答
0

O(n)您可以在时间和O(n)额外空间中解决这个问题。

算法如下。

  1. 将替代项的差异存储在新的大小数组中n-1
  2. 现在遍历新数组并检查替代项的乘积是否小于零。
  3. 相应地增加结果。如果在遍历时发现数组的乘积大于零，则在这种情况下存储结果并再次开始计算差异数组中的其余元素。
  4. 找出其中的最大值，将其存储到结果中，然后return (result+1)

这是它在 C++ 中的实现

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int> data(n);
    for(int i = 0; i < n; i++)
        cin>>data[i];
    vector<int> diff(n-1);
    for(int i = 1; i < n; i++)
        diff[i-1] = data[i]-data[i-1];
    int res = 1;
    if( n < 2)
        cout<<res<<"\n";
    else
    {
        int temp_idx = 0;
        for(int i = 1; i < n-1; i++)
        {
            if(diff[i]*diff[i-1] < 0)
            {
                temp_idx++;
                res++;
            }
            else
            {
                res = max(res,temp_idx);
                temp_idx = 1;
            }
        }
        cout<<res+1<<"\n";
    }
    return 0;
}
于 2014-11-06T08:26:19.593 回答
0

您可以使用RMQ删除内部 for 循环。当您找到 and 的答案时dp[i][0]，dp[i][1]将其保存在两个 RMQ 树中 - 例如 RMQ 0和 RMQ 1 - 就像您现在对dp数组的两行所做的那样。因此，当您计算 时dp[i][0]，您将值dp[i][0]放在a[i]RMQ 0中的位置上，这意味着存在一个长度dp[i][0]以数字结尾逐渐增加的锯齿形序列a[i]。

然后，为了计算dp[i + 1][0]，您不必遍历 0 和 之间的所有数字i。相反，您可以查询 RMQ 0以获取位置 > 上的最大数字a[i + 1]。这将为您提供以大于当前数字的数字结尾的最长 zig-zag 子序列 - 即可以随着数字 递减而继续递减的最长子序列a[i + 1]。然后，您可以对另一半之字形子序列的RMQ 1执行相同的操作。

由于您可以实现查询复杂度为 的动态 RMQ O(log N)，因此总体复杂度为O(N log N).

于 2012-10-14T12:00:49.687 回答
0

这是一个纯粹的理论解决方案。如果你在学术环境中被问到，站在黑板旁边，这就是你解决问题的方法。

可以使用动态规划创建问题的解决方案：

子问题的形式是：如果我有序列的元素 x，那么以该元素结尾的最长子序列是什么？

然后你可以使用递归调用来计算你的解决方案，它应该看起来像这样（关系的方向可能是错误的，我没有检查过）：

S - given sequence (array of integers)
P(i), Q(i) - length of the longest zigzag subsequence on elements S[0 -> i] inclusive (the longest sequence that is correct, where S[i] is the last element)

P(i) = {if i == 0 then 1
   {max(Q(j) if A[i] < A[j] for every 0 <= j < i)


Q(i) = {if i == 0 then 0  #yields 0 because we are pedantic about "is zig the first relation, or is it zag?". If we aren't, then this can be a 1.
   {max(P(j) if A[i] > A[j] for every 0 <= j < i)

这应该是O(n)正确的记忆（存储 Q(i) 和 P(i) 的每个输出），因为每个子问题只计算一次n*|P| + n*|Q|：

这些调用返回解决方案的长度——只要找到最大值，就可以通过存储“父指针”找到实际结果，然后在这些指针上向后遍历。

您可以简单地通过用数组查找替换函数调用来避免递归：P[i]和Q[i]，并使用for循环。

于 2016-06-14T07:06:13.643 回答