0

我正在编写一个简单的程序来计算字符串序列中字符的重复。我现在拥有的程序如下，但我希望看看它是否可以进一步优化。我相信现在的程序是 O(n) 最坏情况时间，我想看看是否有什么东西可以给我 O(log n) 运行时间。

using System;
using System.Collections.Generic;

namespace Algos
{
    class CharacterRepitition
    {
        private char[] checkStringArray;
        private bool[] discovered;

        public CharacterRepitition(string toCheck)
        {
                checkStringArray= toCheck.ToCharArray();           
                discovered= new bool[checkStringArray.Length];
                for (int i = 0; i < checkStringArray.Length; i++)
                {
                    discovered[i] = false;
                }
        }

        public void CheckRepetitions()
        {
            int charIndex=0;
            Dictionary<char, int> repetitions = new Dictionary<char, int>();
            while (charIndex < checkStringArray.Length)
            {
                int count = 0;

                if(discovered[charIndex].Equals(false))
                {
                    count = RunThroughTheString(charIndex, checkStringArray);
                    if (count > 0)
                    {
                        repetitions.Add(checkStringArray[charIndex], count+1);
                    }
                }
                charIndex++;
            }

            if (repetitions.Count == 0)
            {
                Console.WriteLine("\nNo characters repeated.");
            }
            else
            {
                foreach (KeyValuePair<char, int> result in repetitions)
                {
                    Console.WriteLine("\n'"+ result.Key + "' is present: " + result.Value + " times.");
                }
            }
        }

        private int RunThroughTheString(int currentCharIndex, char[] checkStringArray)
        {
            int counter = 0;
            for (int i = 0; i < checkStringArray.Length; i++)
            {
                if (checkStringArray[currentCharIndex].Equals(checkStringArray[i]) && i !=currentCharIndex)
                {
                    counter++;
                    discovered[i] = true;
                }
            }
            return counter;
        }

    }
}

我知道我也可以使用 LINQ 来实现这一点。但这不是我要找的东西。感谢你的帮助。

4

2 回答 2

3

不确定我是否正确阅读了这个问题，但这是否适用于您的情况

    public void FindCharRepetitions(string toCheck)
    {
        var result = new Dictionary<char, int>();
        foreach (var chr in toCheck)
        {
            if (result.ContainsKey(chr))
            {
                result[chr]++;
                continue;
            }
            result.Add(chr, 1);
        }

       foreach (var item in result)
       {
           Console.WriteLine("Char: {0}, Count: {1}", item.Key, item.Value);
       }
    }
于 2013-02-16T22:30:35.073 回答
0

如果已知不同字符的数量（比如只有 AZ），那么代码可能是这样的：

int[] counters = new int['Z' - 'A' + 1];
foreach(char c in toCheck)
    if (c >= 'A' && c <= 'Z')
        counters[c - 'A']++;
于 2013-02-16T22:43:42.000 回答