7

拜托，既然我已经重写了这个问题，并且在它受到进一步的快速回答或急切的编辑过早关闭之前，让我指出这不是这个问题的重复。我知道如何从数组中删除重复项。

这个问题是关于从数组中删除序列，而不是严格意义上的重复。

考虑数组中的这个元素序列；

[0] a
[1] a
[2] b
[3] c
[4] c
[5] a
[6] c
[7] d
[8] c
[9] d

在这个例子中，我想获得以下......

[0] a
[1] b
[2] c
[3] a
[4] c
[5] d

请注意，重复的元素被保留，但相同元素的序列已被简化为该元素的单个实例。

此外，请注意，当两行重复时，它们应减少为一组（两行）。

[0] c
[1] d
[2] c
[3] d

...减少到...

[0] c
[1] d

我正在用 C# 编码，但任何语言的算法都值得赞赏。

4

4 回答 4

3

编辑：做了一些改变和新的建议

推拉窗呢...

REMOVE LENGTH 2: (no other length has other matches)
//the lower case letters are the matches
ABCBAbabaBBCbcbcbVbvBCbcbcAB  
__ABCBABABABBCBCBCBVBVBCBCBCAB

REMOVE LENGTH 1 (duplicate characters):
//* denote that a string was removed to prevent continual contraction
//of the string, unless this is what you want.
ABCBA*BbC*V*BC*AB
_ABCBA*BBC*V*BC*AB

RESULT:
ABCBA*B*C*V*BC*AB == ABCBABCVBCAB

这当然是从长度 = 2 开始，将其增加到 L/2 并向下迭代。

我也在考虑另外两种方法：

  1. digraph - 使用数据设置有状态有向图并使用字符串对其进行迭代，如果发现循环，您将有重复。我不确定检查这些周期有多容易......可能是一些动态编程，所以它可能等同于下面的方法 2。我将不得不考虑这个问题更长的时间。
  2. 距离矩阵- 使用 levenstein 距离矩阵，您可能能够检测到成本为 0 的对角线移动（偏离对角线）的重复。这可能表明数据重复。我将不得不更多地考虑这一点。
于 2008-09-11T17:47:59.247 回答
2

这是我编写的 C# 应用程序，它解决了这个问题。

需要
aabcccdcd

输出
abcacd

可能看起来很乱，花了我一点时间来了解动态模式长度位。

class Program
{
    private static List<string> values;
    private const int MAX_PATTERN_LENGTH = 4;

    static void Main(string[] args)
    {
        values = new List<string>();
        values.AddRange(new string[] { "a", "b", "c", "c", "a", "c", "d", "c", "d" });


        for (int i = MAX_PATTERN_LENGTH; i > 0; i--)
        {
            RemoveDuplicatesOfLength(i);
        }

        foreach (string s in values)
        {
            Console.WriteLine(s);
        }
    }

    private static void RemoveDuplicatesOfLength(int dupeLength)
    {
        for (int i = 0; i < values.Count; i++)
        {
            if (i + dupeLength > values.Count)
                break;

            if (i + dupeLength + dupeLength > values.Count)
                break;

            var patternA = values.GetRange(i, dupeLength);
            var patternB = values.GetRange(i + dupeLength, dupeLength);

            bool isPattern = ComparePatterns(patternA, patternB);

            if (isPattern)
            {
                values.RemoveRange(i, dupeLength);
            }
        }
    }

    private static bool ComparePatterns(List<string> pattern, List<string> candidate)
    {
        for (int i = 0; i < pattern.Count; i++)
        {
            if (pattern[i] != candidate[i])
                return false;
        }

        return true;
    }
}

修复了初始值以匹配问题值

于 2008-09-11T19:30:46.020 回答
1

我会将它们全部转储到您最喜欢的 Set 实现中。

编辑：既然我理解了这个问题，那么您的原始解决方案看起来是最好的方法。只需遍历数组一次，保留一组标志来标记要保留的元素，加上一个计数器来跟踪新数组的大小。然后再次循环以将所有守护者复制到一个新数组中。

于 2008-09-11T16:12:23.610 回答
0

我同意，如果您可以将字符串转储到 Set 中，那么这可能是最简单的解决方案。

如果由于某种原因您无法访问 Set 实现，我只会按字母顺序对字符串进行排序，然后遍历一次并删除重复项。如何对它们进行排序并从列表中删除重复项将取决于您运行代码的语言和环境。

编辑：哦，ick....根据您的说明，我看到您希望模式甚至可能出现在单独的行上。我的方法不能解决你的问题。对不起。这是一个问题。如果我有以下文件。

一种

一种

b

C

C

一种

一种

b

C

C

您是否希望它简化为

一种

b

C

于 2008-09-11T16:16:23.710 回答