查找數組中匹配的連續整數

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++){ 
    ...