主页 / 问题 / 656351
Accepted
tretetex
Asked:2020-04-21 02:35:45 +0000 UTC2020-04-21 02:35:45 +0000 UTC

获取唯一的列表值

  • 772

有一个清单：

var list = new List<string> {
    "строка",
    "строка22у", 
    "строкайцвцйй", 
    "текстцвцй", 
    "текст", 
    "текстыауке5"};

您需要删除包含其他元素的元素。那些。删除行строка22у, строкайцвцйй, 因为 текстцвцй分别包含第一行和текстыауке5。因此строка， ,将保留下来текст。

我这样做：

int removedCount;
do
{
    removedCount = 0;
    for (int i = 0; i < list.Count; i++)
    {
        removedCount += list.RemoveAll(x => x.Contains(list[i]) && x != list[i]);
    }
} while (removedCount != 0);

有没有更有效的方法？

c#

2 个回答

  1. for (int i = 0; i < list.Count; i++)
{
  for (int j = list.Count - 1; j >= 0; j--)
  {
    if (list[j].Contains(list[i]) && list[i] != list[j])
    {
      list.RemoveAt(j);
      if (j < i)
        i--;
    }
  }
}
    • 3
  2. Best Answer

    对于大量字符串（尤其是如果其中许多具有相同的前缀），构建前缀树并在其中搜索应该会更快。然而，更多的代码出来了。

    实施选项。搜索所需字符串的方法：

    private static List<string> dfa(List<string> list)
{
    var result = new List<string>();
    State root = new State();
    foreach (string word in list)
    {
        State state = root;
        foreach (char c in word)
        {
            state = state.get(c);
        }
        state.isFinal = true;
    }
    foreach (string word in list)
    {
        State state = root;
        int i = 0;
        for (; !state.isFinal && i < word.Length; i++)
        {
            state = state.get(word[i]);
        }
        if (i == word.Length)
        {
            result.Add(word);
        }
    }
    return result;
}

    DFA状态的辅助类，考虑优化：

    private class State
{
    private Dictionary<char, State> transitions;
    public bool isFinal = false;
    private char firstChar;
    private State firstState = null;

    public State get(char c)
    {
        if (firstState != null && firstChar == c)
        {
            return firstState;
        }
        if (firstState == null)
        {
            firstState = new State();
            firstChar = c;
            return firstState;
        }
        if (transitions == null)
        {
            transitions = new Dictionary<char, State>();
        }
        if (transitions.ContainsKey(c))
        {
            return transitions[c];
        }
        State state = new State();
        transitions.Add(c, state);
        return state;
    }
}
    • 3

相关问题