查找数组中匹配的连续整数

Question

给定两个包含整数的数组，找出两个数组中是否存在三个连续整数。 例如：A = [1,4,5,7,2]和B = [3,1,4,5,9]将导致“真”/ 1，因为[1,4,5]存在于两个阵列。

我对此任务的解决方案如下，但我觉得必须有比这更优化的解决方案。

int consecutiveInts(int *a, int sizeA, int *b, int sizeB){ 
    int i, j; 

    // Iterate over every integer in array b for every integer in array a. 
    for (i = 0 ; i < sizeA - 2 ; i++){ 
     for (j = 0 ; j < sizeB - 2 ; j++){ 
      if (a[i] == b[j] && a[i + 1] == b[j + 1] && a[i + 2] == b[j + 2]) 
       return 1; 
     } 
    } 
    return 0; 
} 

Answer 1

对于小型阵列，OP方法是可以的。对于阵列长度m,n它有O(m*n)运行时间。

替代方法使2个值数组排序，然后查找一个公共元素。它有O(m*log2(m) + n*log2(n))运行时间。大数组的速度肯定比OP的代码更快。

typedef struct { 
    int i[3]; 
} int3; 

void Init3(int3 *i3, const int *i, size_t n) { 
    while (n--) { 
    i3[n].i[0] = i[n]; 
    i3[n].i[1] = i[n + 1]; 
    i3[n].i[2] = i[n + 2]; 
    } 
} 

int fcmp(const void *a, const void *b) { 
    return memcmp(a, b, sizeof (int3)); 
} 

bool Pattern3(const int *a, size_t size_a, const int *b, size_t size_b) { 
    if (size_a < 3 || size_b < 3) return false; 

    int3 a3[size_a - 2]; 
    Init3(a3, a, size_a - 2); 
    qsort(a3, size_a - 2, sizeof *a3, fcmp); 

    int3 b3[size_b - 2]; 
    Init3(b3, b, size_b - 2); 
    qsort(b3, size_b - 2, sizeof *b3, fcmp); 

    while (size_a && size_b) { 
    int cmp = fcmp(&a[size_a - 1], &b[size_b - 1]); 
    if (cmp == 0) return true; 
    if (cmp > 0) size_a--; 
    else size_b--; 
    } 
    return false; 
} 

int main() { 
    int A[] = { 1, 4, 5, 7, 2 }; 
    int B[] = { 3, 1, 4, 5, 9 }; 
    printf("%d\n", Pattern3(A, sizeof A/sizeof *A, B, sizeof B/sizeof *B)); 
} 

一种替代将使用bsearch()而不是形成第二int3 b3[]/qsort()。

Answer 2

我认为我不能错，说声明i和j以外的循环是没用的，没有优化。

喜欢的东西：

for (unsigned i = 0; i < sizeA - 2; i++) // i will only exist inside the loop 

会好一点。 我使用无符号类型，因为它是我在使用迭代变量时所采取的一种习惯。我认为这是一个问题，如果你有兴趣并且没有得到通知，你可以通过阅读this的话题来学习。

Answer 3

尝试使用下面的循环

for(int i=0;i<A.length;i++) 
{ 
    for(int j=0;j<A.length;j++) 
    { 
     if(A[i]==B[j]) 
     { 
      count=count+1; //It checks how many times equal elements have been found 
          //ensure to declare and initialize int count=0; 
     } 
    } 
} 
if(count>=3) 
    System.out.println("true"); 

Answer 4

不知道它优化了运行速度，但我注意到，万一出现重复，你不需要一遍又一遍检查它们的数字。

例如，第一个阵列中的三个顺序元素都是1。在检查a[i]并看到它不匹配的情况下，您可以直接跳至a[i + 3]，而无需比较a[i + 1]或a[i + 2]（它们也是不匹配的）。

这种情况的管理，特别是如果它是一个很短的重复序列，可能无法改善运行时间。你必须测量。

Answer 5

对于不影响order of complexity的代码更改，任何候选改进都需要分析（测量性能的测试）来验证。

以下依然是O（n * m），但系数降低，因为如果a[]具有也存在于b[]中的重复值，则它可以更快地步进b[]。这加速了大部分时间消耗的内部循环。

---

看为不同的值的a[]图案如此j可以推进更快。
例子：

#define x 0 
bool Pattern3(const int *a, size_t size_a, const int *b, size_t size_b) { 
    static const unsigned char deltas[2][2][2][2] = { // 
     //     What type of pattern is a[0], a[1], a[2]? 
     { { { 1, 1 }, // X Y Z 
     { 1, 1 } },  // X Y Y 
     { { 1, 2 },  // X Y X 
     { x, x } } }, // not possible 
     { { { 2, 1 }, // X X Y 
     { x, x } },  // not possible 
     { { x, x },  // not possible 
     { 2, 3 } } } }; // X X X 
    for (unsigned i = 0; i + 2 < size_a; i++) { 
    const unsigned char *delta23 = deltas[a[0] == a[1]][a[0] == a[2]][a[1] == a[2]]; 
    for (unsigned j = 0; j + 2 < size_b;) { 
     if (a[0] != b[j]) { 
     j++; 
     } else if (a[0 + 1] != b[j + 1]) { 
     j += delta23[0]; 
     } else if (a[0 + 2] != b[j + 2]) { 
     j += delta23[1]; 
     } else { 
     return true; 
     } 
    } 
    a++; 
    } 
    return false; 
} 

---

其他小的变化，这可能会有帮助。

在上面，交换a,b时size_a > size_b。

使用const作为更少的编译器可以优化。

// int consecutiveInts(int *a, int sizeA, int *b, int sizeB){ 
int consecutiveInts(const int *a, int sizeA, const int *b, int sizeB){ 

从2开始迭代。相应地调整索引。

for (i = 2 ; i < sizeA ; i++){ 
    ...