查找最常見的對字符的字符串中的

我寫以下函數查找最常見的對字符的字符串中的

//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

查找最常見的對字符的字符串中的

回答

相關問題