在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）时间查找频繁发生的字母？

回答

相关问题