寻找数组重复单元的最简单方法是什么？

Question

例如，

1,1,1,1,1 

重复单元为1

1,3,2,1,3,2,1,3,2 

重复单元是

1,3,2,1,3,9,1,3,2 

1,3,2

重复单元

是1,3,2,1,3,9,1,3,2

我尝试的想法是这样的：从1重复单元测试的

1.try数，直到阵列的大小

2.仅尝试这是阵列的尺寸，例如多个编号：n

3.检查如果n是重复单元的大小，例如：假设测试重复单元为3，则检查是否

a[0]==a[3*1],a[1]==a[1+3*1],a[2]==a[2+3*1] 
a[0]==a[3*2],a[1]==a[1+3*2],a[2]==a[2+3*2] 
a[0]==a[3*r],a[1]==a[1+3*r],a[2]==a[2+3*r] 

1. 如果当前测试号是重复单元，休息一下，我的当前值是重复单元的大小

我尝试将其转换为代码：

#include <stdio.h> 
int main(){ 
    int a[]={1,3,2,1,3,2,1,3,2}; 
    int i; 
    //1.try number of repeat unit test from 1,until the size of array 
    for(i=1;i<=sizeof(a)/sizeof(int);i++){ 
     //2.only try number which is multiple of the size of array,e.g.: n 
     int n=sizeof(a)/sizeof(int); 
     if(n%i==0){ 
      //3.check if n is the size of repeat unit 
      bool isRepeat=true; 
      for(int j=0;j<n;j++){ 
       for(int r=1;r<i;r++){ 
        if(a[j]!=a[j+r*n]){ 
         isRepeat=false; 
         break; 
        } 
       } 
      } 
      //4.if the current testing number is repeat unit, break, and the current value of i is the size of repeat unit 
      if(isRepeat){ 
       break; 
      } 
     } 
    } 

    //print the result using repeat unit n 
    for(int n=0;n<i;n++){ 
     printf("%d ",a[n]); 
    } 
}; 

，但它显示了重复单元的1,3,2,1,3,2,1,3,2是1而不是1,3,2。我认为这个解决方案的想法太复杂了，因为它有太多for循环。有更简单的方法或算法来找到数组的重复单位吗？

Answer 1

看来你已经在if(a[j]!=a[j+r*n])

一个bug你们为何n增加吗？它不应该是：if(a[j]!=a[j+r*i])？

此外，算法有点慢，另一种解决方法是将每个数字视为字符串中的不同字符，并使用Knuth Morris-Pratt（KMP）算法。 （https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm）

稍后会为答案增加更多信息。

UPDATE：

免责声明：语法和变量可能是不完整

KMP实现：

int F[MAX_N]; 
int main(void){ 
    int P[MAX_N], T[MAX_N]; 
    //1. get input, put it into P array, not coded. 
    //.... 
    //2. insert content of P array to T twice. 
    int ptr = 0; 
    for(int i = 0;i<2;i++) 
     for(int j = 0;j<length_of_p;j++){ 
      T[ptr++] = P[j]; 
     } 
    //3. get length of repeated unit. 
    int repeated = kmp(P, T, 1); 
    //4. print the numbers of repeated unit. i.e. done 
    cout<<"REPEATED UNIT: "; 
    for(int i = 0;i<repeated;i++) 
     cout<< P[i] << " "; 
    cout<<endl; 

    return 0; 
} 
void kmp_init(int P[]) { 
    F[0] = 0; F[1] = 0; 
    int i = 1, j = 0; 
    while(i<P.size()) { 
     if (P[i] == P[j]) 
      F[++i] = ++j; 
     else if (j == 0) 
      F[++i] = 0; 
     else 
      j = F[j]; 
    } 
} 

int kmp(int P[], int T[], int start) { 
    kmp_init(P); 
    int i = start, j = 0; 
    int n = T.size(), m = P.size(); 

    while(i-j <= n-m) { 
     while(j < m) { 
      if (P[j] == T[i]) { 
       i++; j++; 
      } else break; 
     } 
     if (j == m) return i-m; 
     else if (j == 0) i++; 
     j = F[j]; 
    } 
} 

Answer 2

这里的错误是事实，你先检查情况当我是1，当然这将被视为你的重复单位。 这是因为该行

for(int r=1;r<i;r++) 

将立即打破，如果i=1（你的第一种情况）。

如果你确定你的数字在0到9之间（即只有一个数字），并且你想要一个“简单”的解决方案（就像你在标题中说的那样），你可以用数字来构建一个字符串，将字符串拆分为子字符串，并检查它们是否全部相等。

#include <stdio.h> 
#include <string.h> 

int main(){ 
    int nums[]={1,3,2,1,3,2,1,3,2}; 
    char initial_string[255]; 
    char string_list[255][255]; 
    int i, j, k, l; 
    int found = 0; 

    memset(initial_string, 0, 255); 
    for(i=0; i < sizeof(nums)/sizeof(int); i++) { 
     initial_string[i] = '0' + nums[i]; 
    } 

    int n = sizeof(nums)/sizeof(int); 
    memset(string_list, 0, 255*255); 

    for(i = 1; i <= n; i++) { 
     if (n%i == 0) { 
      int count = (int)n/i; 
      for (k = 0, j = 0; k < n; k+=i, j++) { 
       strncpy(string_list[j], &initial_string[k], i); 
      } 
      found = 1; 
      for (k = 0; k < count; k++) { 
       if (strcmp(string_list[0], string_list[k])) { 
        // Different strings! 
        found = 0; 
        break; 
       } 
      } 
     } 
     if (found) { 
      break; 
     } 
    } 

    printf("Repeat unit: %d\n", i); 
} 

请注意，此代码是不最优，有几件事情来改善，把它作为一个总体思路。

Answer 3

您可以在这里使用STL设置功能。像这样，

int main() 
{ 
set<int> s; 
    s.insert(1); 
    s.insert(3); 
    s.insert(2); 
    s.insert(1); 
    s.insert(3); 
    s.insert(2); 
    s.insert(1); 
    s.insert(3); 
    s.insert(2); 

    set<int> :: iterator it; 
    for(it = s.begin(); it != s.end(); it++) { 
    cout << *it << endl; 
} 

它会打印不同的元素，因此你会发现任何数组的重复单元。 快乐编码！