5

我写了以下功能

//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 ch2 = s 数量 = 4

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

4

4 回答 4

5

由于char最多可以容纳 256 个值，因此您可以设置一个 [256*256] 计数器的二维表，遍历您的字符串一次，递增对应于字符串中每对字符的计数器。然后，您可以浏览 256x256 数字表，选择最大的计数，并通过查看其在 2D 数组中的位置来了解它属于哪对。由于计数器表的大小固定为与字符串长度无关的常数值，因此该操作是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]);

这是ideone 上演示的链接。

请记住，虽然这是渐近的最快可能解决方案（即它是O(N)，并且你不能让它比 更快O(N)），但对于较短的字符串来说，性能并不好。事实上，您的解决方案可以轻松应对少于大约 256 个字符的输入，甚至可能更多。有许多优化可以应用于此代码，但我决定不添加它们以保持代码的主要思想以其最纯粹和最简单的形式清晰可见。

于 2012-12-20T20:18:11.360 回答
4

如果您想要O(n)运行时，您可以使用哈希表（例如，Java 的HashMap）

  • 遍历你的字符串一次，一次 1 个字符O(n)
  • 对于访问的每个字符，向前看正好 1 个字符（这就是你的字符对 - 只需将它们连接起来）O(1)
  • 对于找到的每个这样的字符对，首先在哈希表中查找它：O(1)
    • 如果它还没有在哈希表中，请将其添加到字符对作为键和int 1值（这会计算您在字符串中看到它的次数）。O(1)
    • 如果它已经在哈希表中，则增加其值O(1)
  • 浏览完字符串后，检查哈希表中计数最高的对。O(m)（其中m是可能配对的数量；m <= n必然）
于 2012-12-20T20:23:27.243 回答
1

是的，您可以通过保持运行计数在近似线性的时间内完成此操作。

这有帮助吗？

于 2012-12-20T20:17:10.107 回答
0

假设大多数“常见对”是指最常见的两个连续字符集

在您想要的伪代码级别

 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

因此，您需要一种有效的算法来存储和计数与字符对相关联的字符，并找到最常见的字符对。

于 2012-12-20T20:20:28.940 回答