查找最常见的对字符的字符串中的

我写以下函数查找最常见的对字符的字符串中的

//O(n^2) 
void MostCommonPair(char * cArr , char * ch1 , char * ch2 , int * amount) 
{ 
    int count , max = 0; 
    char cCurrent , cCurrent2; 
    int i = 0 , j; 
    while(*(cArr + i + 1) != '\0') 
    { 
     cCurrent = *(cArr + i); 
     cCurrent2 = *(cArr + i + 1); 
     for(j = i , count = 0 ; *(cArr + j + 1) != '\0' ; j++) 
     { 
      if(cCurrent == *(cArr + j) && cCurrent2 == *(cArr + j + 1)) 
      { 
       count++; 
      } 
     } 
     if(count > max) 
     { 
      *ch1 = cCurrent; 
      *ch2 = cCurrent2; 
      max = *amount = count; 
     } 
     i++; 
    } 
}

以下输入

“xdshahaalohalobscxbsbsbs”

CH1 = B CH 2 = S量= 4

但在我看来，这个函数效率很低，有没有办法只通过一次字符串或将运行大小减少到O（n）？

来源

2012-12-20 Daniel Hallel

说明该OP正在寻找的字符具有最高计数的连续对。 – hatchet

由于char最多可容纳256个值，因此您可以设置[256 * 256]个计数器的二维表，通过您的字符串运行一次，递增对应于字符串中每对字符的计数器。然后你可以浏览256x256的数字表格，选择最大的数字，并通过查看它在二维数组中的位置知道它属于哪一对。由于计数器表的大小固定为与字符串长度无关的恒定值，因此该操作为O(1)，即使它需要两个嵌套循环。

int count[256][256]; 
memset(count, 0, sizeof(count)); 
const char *str = "xdshahaalohalobscxbsbsbs"; 
for (const char *p = str ; *(p+1) ; p++) { 
    count[(int)*p][(int)*(p+1)]++; 
} 
int bestA = 0, bestB = 0; 
for (int i = 0 ; i != 256 ; i++) { 
    for (int j = 0 ; j != 256 ; j++) { 
     if (count[i][j] > count[bestA][bestB]) { 
      bestA = i; 
      bestB = j; 
     } 
    } 
} 
printf("'%c%c' : %d times\n", bestA, bestB, count[bestA][bestB]);

这是link to a demo on ideone。请注意，虽然这是最快的解决方案（即它是O(N)，并且您无法使其速度快于O(N)），但对于较短的字符串，性能不会太好。事实上，您的解决方案将在大约256个字符以内的输入中胜出，甚至更多。有很多优化可以应用到这个代码中，但是我决定不添加它们来保持代码的主要思想以最纯粹和最简单的形式清晰可见。

来源

2012-12-20 20:18:11 dasblinkenlight

但计数最高的两个字符可能不会在字符串中的任何位置配对。他正在寻找最高的一对。 – hatchet

@hatchet啊，你是对的。这现在已经修复。 – dasblinkenlight

这是O（n），但有些输入的性能会很差。对于这种算法，它是简短的字符串。一串5个字符，它将遍历5个字符，然后遍历65K个计数。 – hatchet

是的，你可以通过保持运行计数大致线性的时间来做到这一点。

这有帮助吗？

来源

2012-12-20 20:17:10 Useless

大多数“共同对”假设你的意思是最常见的一组两个连续的字符

在伪代码级别要

Read the first character into the "second character" register 
while(there is data) 
    store the old second character as the new first character 
    read the next character as the second one 
    increment the count associated with this pair 
Select the most common pair

所以，你需要的是一个有效的algorythm用于存储和计数与字符对相关联并找到最常见的一个。

来源

2012-12-20 20:20:28 dmckee

如果你想为O（n）运行时，你可以通过你的字符串中使用一个hashtable（例如，Java的HashMap）

迭代只出现一次，每次O（n）的1个字符
对于每个角色在走访中，向前看，正好1个字元（这是这样你的性格对 - 只是将它们连接起来）O（1）
对于每一次这样CHARAC之三对发现，先来看看它在哈希表：O（1）
- 如果它不是在哈希表的是，与字符对作为键添加它，并int 1作为值（这个计数您在字符串中看到过的次数）。 O（1）
- 如果它已经在哈希表中，增加它的价值O（1）
你做翻翻字符串后，检查一对具有最高计数哈希表。 O（米）（其中m是可能配对的数量; 一定）

来源

2012-12-20 20:23:27

查找最常见的对字符的字符串中的

回答

相关问题