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 に答える