Самый быстрый способ реализовать удаление повторяющихся символов в строке (C #) - PullRequest
Новая
       13

Самый быстрый способ реализовать удаление повторяющихся символов в строке (C #)

8 голосов
/ 28 августа 2009

В C #, какой самый быстрый способ обнаружить повторяющиеся символы в строке и удалить их (удаление , включая 1-й экземпляр дублированного символа)?

Пример ввода: nbHHkRvrXbvkn

Пример вывода: RrX

Ответы [ 5 ]

21 голосов
/ 28 августа 2009

Самый быстрый как в наименьшем количестве строк кода: 

var s = "nbHHkRvrXbvkn";
var duplicates = s.Where(ch => s.Count(c => c == ch) > 1);
var result = new string(s.Except(duplicates).ToArray()); // = "RrX"

Быстрее всего в быстродействии, вероятно, что-то вроде этого (не сохраняет порядок): 

var h1 = new HashSet<char>();
var h2 = new HashSet<char>();

foreach (var ch in "nbHHkRvrXbvkn")
{
    if (!h1.Add(ch))
    {
        h2.Add(ch);
    }
}

h1.ExceptWith(h2); // remove duplicates

var chars = new char[h1.Count];
h1.CopyTo(chars);
var result = new string(chars); // = "RrX"

Тест производительности

Если сомневаешься - проверь это:) 

Yuriy Faktorovich's answer        00:00:00.2360900
Luke's answer                     00:00:00.2225683
My 'few lines' answer             00:00:00.5318395
My 'fast' answer                  00:00:00.1842144
9 голосов
/ 28 августа 2009

Вот довольно быстрый сохраняющий порядок. Но я бы немного беспокоился о том, как LINQ делает Group и где: 

string s = "nbHHkRvrXbvkn";
Console.WriteLine( 
    s.ToCharArray()
        .GroupBy(c => c)
        .Where(g => g.Count() == 1)
        .Aggregate(new StringBuilder(), (b, g) => b.Append(g.Key)));

Редактировать: Этот в некоторых случаях побеждает Люка все еще медленнее, чем ДТБ, но сохраняет порядок 

private static string MyMethod(string s)
{
    StringBuilder sb = new StringBuilder(s.Length);
    foreach (var g in s.ToCharArray().GroupBy(c => c))
        if (g.Count() == 1) sb.Append(g.Key);

    return sb.ToString();
}
4 голосов
/ 28 августа 2009

Это должно быть довольно быстро (и оно сохраняет первоначальный порядок): 

public static string RemoveDuplicates(string source)
{
    HashSet<char> found = new HashSet<char>();
    HashSet<char> dupes = new HashSet<char>();

    foreach (char c in source)
    {
        if (!found.Add(c))
        {
            dupes.Add(c);
        }
    }

    StringBuilder sb = new StringBuilder(source.Length);
    foreach (char c in source)
    {
        if (!dupes.Contains(c))
        {
            sb.Append(c);
        }
    }
    return sb.ToString();
}
2 голосов
/ 28 августа 2009

Это сохраняет порядок и, согласно моим тестам, в 4 раза быстрее, чем использование HashSet. Это предполагает, что ваш диапазон символов составляет 0-255, но вы можете легко это расширить. Если вы планируете использовать это в цикле, переместите int[] c = new int[255]; и в функции выполните Array.Clear(c,0,255). 


        private static string RemoveDuplicates(string s)
        {
            int[] c = new int[255];
            for (int i = 0; i < s.Length; i++)
            {
                c[s[i]]++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.Length; i++)
            {
                if (c[s[i]] == 1) sb.Append(s[i]);
            }
            return sb.ToString();
        }
0 голосов
/ 28 августа 2009

Этот алгоритм является общим, может применяться к любому языку

  1. создать карту (HashTable) char-> int, которая содержит количество найденных символов, изначально пустых
  2. отсканируйте строку один раз, чтобы заполнить карту.
  3. создайте новую пустую строку, которая будет содержать выходные данные, возможно, вам потребуется использовать StringBuilder.
  4. сканировать строку (или карту, в зависимости от того, что короче), копируя только символы, которые встречаются как 1, в выходную строку / StringBuilder
...