如何在C# .Net中查找字符串中的偶数重复字符。

Question

我有一个问题，如何在C#中删除字符串中的偶数重复项。

例如-输入字符串：

acdhqodcqasaf

输出：

acdhqosaf

我的意思是删除字符的偶数次出现。我已经写了逻辑，但是我使用了嵌套的for循环，效率为O(n^2)，这个效率不好。所以我被要求用不同的方法来解决这个问题，搜索了一下网络，但还没有找到答案。

- Vadiya

---

什么是偶数重复项？ - Tim Schmelter

我已经编写了逻辑。你介意与我们分享吗？ - Heretic Monkey

当然，我会分享-@Heretic。 - Vadiya

@Brian 我认为这不是错误的。如果我理解正确，OP想要删除每个字符的第二个出现 - 因此，如果该字符在输入中出现三次（a确实如此），它应该在输出中出现两次。 - Zohar Peled

我编辑了我的回答，请看一下。 - Ashkan Mobayen Khiabani

Answer 1

您可以使用字典来跟踪出现次数，并使用% 运算符：

string input = "acdhqodcqasaf";
var charOccurences = new Dictionary<char, int>();
int removeEvery = 2;
var outputBuilder = new StringBuilder();

foreach (char c in input)
{
    charOccurences.TryGetValue(c, out int charOccurence);
    charOccurence++;
    charOccurences[c] = charOccurence;
    if (charOccurence % removeEvery != 0)
        outputBuilder.Append(c);
}

string output = outputBuilder.ToString();

- Tim Schmelter

Answer 2

我会使用HashSet来跟踪您已经看到了奇数次的字符。

string input = "acdhqodcqasaf";
var oddOccurrences = new HashSet<char>();
var output = new StringBuilder();
foreach (var c in input)
{
    if (!oddOccurrences.Contains(c))
    {
        output.Append(c);
        oddOccurrences.Add(c);
    }
    else
    {
        oddOccurrences.Remove(c);
    }
}
Console.WriteLine(output.ToString());

- StriplingWarrior

---

不错。现在删除每三个 :)。 - Tim Schmelter

请注意，通过在添加或删除时使用 bool 返回可以稍微提高性能，避免调用 Contains，但我觉得这会降低方法的可读性。 - StriplingWarrior

@TimSchmelter：哈哈，是的。你可以使用字典来跟踪出现的次数，并使用任意标准计数来确定是否输出该值。 - StriplingWarrior

是的，为了完整起见，我提供了这个字典方法。 - Tim Schmelter

Answer 3

你可以遍历数组，使用一个 dictionary<char,int> 来计算每个字符的出现次数。检查计数以确定是否删除该字符或将其添加到结果字符串中。

- AD.Net

Answer 4

创建一个bool[]，用于为您跟踪奇数和偶数：

bool[] even = new bool[256];
string input = "acdhqodcqasaf";
string output = "";
for(int i=0;i<input.Length;i++)
{
    int x = (int)input[i];
    if(!even[x])output += input[i];
    even[x] = !even[x];
}

将 bool[256] 更改为 bool[256*256]，以支持16位字符。

演示实况

- Ashkan Mobayen Khiabani

---

比我的 HashSet 方法稍微快一点，但它假设所有 char 值都在 0-255 的值范围内。 - StriplingWarrior

没错，在C#中字符是16位的 ;) - Ian

Answer 5

只是为了好玩，我用秒表记录了这个问题的顶级答案，并添加了一个Distinct方法：

return new string(input.Distinct().ToArray());

输出结果很有趣（10k次运行）：

ASDHFAJSHKDFASJDFHJgasdfkjhasdjhfashdfkjasdjkfajkhewkjrhwakhfuiwhfsdnfvjndfsjkgnklwerjliu4596945
Distinct 344
RunForEach1 551
RunForEach2 522
RunFor 454

当运行10k次时，distinct似乎获胜（在速度方面），尽管运行100次结果非常不同：

ASDHFAJSHKDFASJDFHJgasdfkjhasdjhfashdfkjasdjkfajkhewkjrhwakhfuiwhfsdnfvjndfsjkgnk
Distinct 9
RunForEach1 7
RunForEach2 1
RunFor 1

代码：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine();
            var sw = new System.Diagnostics.Stopwatch();

            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                RunDistinct(input);
            }
            sw.Stop();
            Console.WriteLine($"Distinct {sw.ElapsedMilliseconds}");

            sw.Reset();
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                RunForEach1(input);
            }
            sw.Stop();
            Console.WriteLine($"RunForEach1 {sw.ElapsedMilliseconds}");

            sw.Reset();
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                RunForEach2(input);
            }
            sw.Stop();
            Console.WriteLine($"RunForEach2 {sw.ElapsedMilliseconds}");

            sw.Reset();
            sw.Start();
            for (int i = 0; i < 100000; i++)
            {
                RunFor(input);
            }
            sw.Stop();
            Console.WriteLine($"RunFor {sw.ElapsedMilliseconds}");

            Console.ReadKey();
        }


        private static string RunDistinct(string input) {
            return new string(input.Distinct().ToArray());
        }

        private static string RunForEach1(string input) {
            var charOccurences = new Dictionary<char, int>();
            int removeEvery = 2;
            var outputBuilder = new StringBuilder();

            foreach (char c in input)
            {
                charOccurences.TryGetValue(c, out int charOccurence);
                charOccurence++;
                charOccurences[c] = charOccurence;
                if (charOccurence % removeEvery != 0)
                    outputBuilder.Append(c);
            }

            return outputBuilder.ToString();
        }

        private static string RunForEach2(string input)
        {
            var oddOccurrences = new HashSet<char>();
            var output = new StringBuilder();
            foreach (var c in input)
            {
                if (!oddOccurrences.Contains(c))
                {
                    output.Append(c);
                    oddOccurrences.Add(c);
                }
                else
                {
                    oddOccurrences.Remove(c);
                }
            }
            return output.ToString();
        }

        private static string RunFor(string input)
        {
            bool[] even = new bool[256];
            string output = "";
            for (int i = 0; i < input.Length; i++)
            {
                int x = (int)input[i];
                if (!even[x]) output += input[i];
                even[x] = !even[x];
            }

            return output;
        }
    }
}

- Ralf de Kleine