重复字符

我正在写一个简单的程序来计算字符串序列中字符的重复。我现在的程序如下，但我期待看看它是否可以进一步优化。我相信现在的程序是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来实现这一点。但那不是我正在寻找的东西。感谢你的帮助。

来源

2013-02-16 Muqeet Khan

它必须是'O（n）'，因为必须经过每个角色。我不明白你甚至可以从理论上减少这种情况。 – Oded 2013-02-16 22:06:33

只有这个代码看起来高于O（n）..？但我不知道如何改进这个想法。 – 2013-02-16 22:09:46

@Cicada你能让我知道我能做些什么来改善这个代码吗？是的，我可以理解O（n）运行时间背后的逻辑。 – 2013-02-16 22:23:43

不知道如果我读正确的问题，但这样做的工作在你的情况

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-16 22:30:35

是@ sa_ddam213 ...我的程序是O（nlgn），正如Corey指出的那样...这是O（n）...谢谢！ – 2013-02-16 22:42:21

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

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

来源

2013-02-16 22:43:42 Casperah

回答

相关问题