如何減少空間「isUniqueString」

我寫了下面的isUniqueCharsInString如何減少空間「isUniqueString」

public static bool isUniqueCharsInString(String str) 
     { 
      int[] charsCount = new int[256]; 
      for (int i = 0; i < charsCount.Length; i++) 
      { 
       charsCount[i] = 0; 
      } 
      for (int i = 0; i < str.Length; i++) 
      { 
       int val = str[i]; 
       charsCount[val] = charsCount[val] + 1; 
       if (charsCount[val] > 1) 
       { 
        return false; 
       } 

      } 
      return true; 

     }

雖然它的工作well.How可我降低其空間複雜度，使最小的內存在運行時可能使用的複雜性。問候。

來源

2014-02-08 user3266922

你要明白，這個代碼不用於字符（擴展）ASCII範圍之外的工作？ –

是的，我知道， – user3266922

爲了儘量減少空間複雜度使用byte[]或bool您charsCount甚至更好BitArray，因爲你只能用它來設置標誌：

public static bool isUniqueCharsInString(String str) 
{ 
    var charsCount = new BitArray(256); 
    for (int i = 0; i < str.Length; i++) 
    { 
     int val = str[i]; 
     if (charsCount[val]) 
     { 
      return false; 
     } 
     charsCount[val] = true; 
    } 
    return true; 
}

一個有趣的使用LINQ另一種方法：

public static bool isUniqueCharsInString1(String str) 
{ 
    return str.ToCharArray().GroupBy(c => c).All(g => g.Count() <= 1); 
}

它在空間和時間上都沒有得到優化，但更加簡潔和易於理解。

出curisity的：你爲什麼如此擔心空間的複雜性？您的原始實施僅使用1 KB陣列（256 * 4 B）。

來源

2014-02-08 15:17:11

它在實際我被方式處理一個非常大的字符串中的字符只是一個例子，你的代碼是我很難理解，如果你有時間在未來取悅點點精心it.Thanx – user3266922

@ user3266922的第二個可能？它首先將字符串轉換爲'IEnumerable的'要能使用LINQ，然後我組收集的個性值，並在最後一步我數出現次數爲每個不同的字符的數量，儘快返回false作爲一個發生多比一次。 –

精美完成。它讓我想起了SQL中的group by clause。 – user3266922

如何減少空間「isUniqueString」

回答

相關問題