在log（n）時間查找頻繁發生的字母？

-1

如果給出一個字符串，比如「aaabbccc」，你會如何輸出'a'，因爲它和'c'一樣頻繁出現，但是首先出現。在log（n）時間查找頻繁發生的字母？

我使用O（n）時間做了它，但我無法弄清楚如何使用log（n）時間來做到這一點，無論是在Java或c + +。編輯：這是一個面試問題。

#include <iostream> 
#include <string> 
using std::string; 
using std::cout; 
using std::cin; 
using std::endl; 

char findFreqChar(string str) { 
    int count; 
    int maxOccur = 0; 
    char maxChar; 
    for (char i = 'A'; i < 'z'; i++) { 
     count = 0; 

     for (int j = 0; j < str.length(); j++) { 
      if (i == str[j]) 
       count++; 
     } 
     if (count > maxOccur) { 
      maxOccur = count; 
      maxChar = i; 
     } 
    } 
    return maxChar; 
} 
int main() { 
    std::cout << "Enter String: "; 
    std::string str; 
    std::getline(std::cin, str); 
    cout << findFreqChar(str); 
    cin.get(); 
}

來源

2015-04-02 user3821306

拆分它？並繼續分裂它？ – 3kings 2015-04-02 16:34:15

此問題更適合http://cs.stackexchange.com/。 – jean 2015-04-02 16:35:04

我很確定，這不是如何制定面試問題。 – 2015-04-02 17:31:49

有沒有辦法找到最頻繁的信件在不到O(n)時間，因爲你不能確定該信息，而無需檢查字符串中的每個字符！

來源

2015-04-02 16:50:38

如果您可以保證字母排序（如您的示例中所示），那麼您可以使用二進制搜索來識別每個連續字母範圍的末尾。每個二進制搜索將是log（n）;最壞的情況下，你需要做25個查找所有的邊界，但是「25 x constant x log（n）」仍然是O（log（n））。

如果採用二分法搜索方法，那麼可以巧妙地做到這一點 - 在相同的二分搜索中連續測試返回相同的字母，並假設作爲最小範圍大小，然後中止任何可能的更短的範圍比那更好 - 但是你可能會更好地使用單獨的搜索進行編碼。或者可能更好的是採取O（n）掃描解決方案：你真的需要這樣做O（log（n））？

來源

2015-04-02 17:08:32 Rup

我不認爲面試提到了一個有序的字符串，就像我給出的例子，但這似乎是最可行的方式。 – user3821306 2015-04-02 17:25:05

如果您需要在O（log（n））時間內完成此操作，則表明您需要開發某種分而治之的算法。我假設（根據你給我們的例子），所有出現的一個字母是連續的。因此，我們可以執行以下操作：

1）將數組拆分成一半並遞歸調用算法。子算法必須返回4個值： - 發生的陣列中的最頻繁的值，並且其頻率 - 中的最右邊的字符結尾的連續字符數 - 中的最左邊的字符

所以結束連續字符數當針對「aabbbbcc」調用時遞歸調用將返回：（b，4，2，2）

2）合併兩個子數組並返回（現在更大的數組）的結果。首先，我們需要計算組合數組中最頻繁的字符。這很容易計算爲右邊的最長序列，左邊最長的序列或跨越分割點的序列（這就是爲什麼我們需要遞歸調用的最後2個值）。這可以全部在恆定時間完成。我們還從兩個遞歸調用中返回適當的值，以獲得以最右邊和最左邊字符結尾的連續字符的長度。

此遞歸結束與T（N）= T（N/2）+ O（1），或O（LG n）的

有相當多的邊界情況來處理，你需要圖在遞歸「底線」時如何處理，但這應該足以讓你編寫代碼。

來源

2015-04-02 17:41:13

在log（n）時間查找頻繁發生的字母？

回答

相關問題