重複字符

Question

我正在寫一個簡單的程序來計算字符串序列中字符的重複。我現在的程序如下，但我期待看看它是否可以進一步優化。我相信現在的程序是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來實現這一點。但那不是我正在尋找的東西。感謝你的幫助。

Answer 1

不知道如果我讀正確的問題，但這樣做的工作在你的情況

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); 
     } 
    } 

Answer 2

如果不同的字符數是已知的（比如說只AZ），那麼代碼可能是這樣的：

int[] counters = new int['Z' - 'A' + 1]; 
foreach(char c in toCheck) 
    if (c >= 'A' && c <= 'Z') 
     counters[c - 'A']++;