[探索 3 分鐘] 檢查字串中最多相同數字的最大數量, 效率型做法 (c#)

Question : 有個固定長度 4 的字串, 內容為數字, 需判斷字串中最多相同數字的最大數量, 有點饒舌, 範例輸出入如下 (input → output)。

• 1314 → 2 (因為 2 個 1)
• 8888 → 4 (因為 4 個 8)
• 5566 → 2 (因為 2 個 5 或 2 個 6)

就是這麼簡單。當下是想到暴力法, 畢竟只有 4 個數字...(其實也沒這麼暴力, 隱含著 divide-and-conquer 的概念)。

public static int MaxSameNumbers(string s)
{
    char[] foo = s.ToArray();
    Array.Sort(foo);
    s = new string(foo);
    
    var l = s.Substring(0, 2);
    var r = s.Substring(2);
    int countL = 1, countR = 1;
    if (l[0] == l[1]) countL = 2;
    if (r[0] == r[1]) countR = 2;
    if (l[1] == r[0])
     return countL + countR;
    else
     return Math.Max(countL, countR);
}

有點囉嗦, 需要先針對字串排序, 如此一來, 左半邊最多 2 個連號, 右半邊也是, 也就是各邊的最大值都在 1 ~ 2 ; 而最後只需要額外再確認是不是中間相連的數字竟也相同。要注意題目不是都 5566, 1314 這種, 還會有 9555, 8888 這種的, 所以解法呢 ? 針對這種中間有相同數字的 case, 把兩邊的最大值加起來即可。但由於真的太囉嗦了, 換一版字典的寫法。

public static int LinqMaxSameNumbers(string s)
{
    var d = new Dictionary<char, int>();
    for(var i = 0; i < s.Length; ++i)
    {
        if (d.ContainsKey(s[i])) ++d[s[i]];
        else d.Add(s[i], 1);
    }
    return d.Values.Max();
}

這版本不需要先 Sort 了, 訪問一次把 K, V 值放到字典裏面, Value 放這個字元出現的次數, 那最後問一下字典先生, 你最大的 Value 值多少不就搞定了 ? LINQ 有個回傳最大 Key 或 Value 的用法類似 d.Keys.Max() 或 d.Values.Max() , 如此一來是不是代碼可讀性高多了 ! 照慣例還是會想知道上面的執行效率如何 ? LINQ 版本估計開銷挺大的吧 ? 跑個 100 萬次來試試。

答案揭曉, 如預期 LINQ 的確最慢, 但非 LINQ 版本也沒多快, 猜看看是慢在哪個地方 ? 程式碼太長 ? SubString() ? Max() ? Sort() ?

有經驗的人可能猜到了, 就是 Sort(), 他吃的時間複雜度是 Big O(nlog(n)) ~ O(log(n^2)), 是很大的開銷。但如果傳進來的值已經是排序好的字串 (也就是不再需要幫它排序), 然後再跑 100 萬次跟 LINQ 比, 差距會拉大多少呢 ?

令人訝異, 足足比原來版本快上一倍。

不過, 衷心建議還是使用字典版吧, 寫法簡潔也是很重要的。而題目雖然這麼說只有 4 個字元, 但把一個函式寫為支持 N 個位元的更通用函式, 才會有人想用的。除了 recursive (更慢的版本), 你還有更好的寫法嗎 ? 歡迎留言分享 ~

參考資料

• https://stackoverflow.com/questions/10290838/how-to-get-max-value-from-dictionary