C程序查找两个数组之间的共同数组元素

这里我们将建立一个C程序来寻找两个数组之间的共同元素。给定两个数组，我们必须用以下两种方法找到它们的共同元素。

1.使用蛮力
2.使用合并排序，然后进行遍历

输入:

array1[] = {8, 2, 3, 4, 5, 6, 7, 1}
array2[] = {4, 5, 7, 11, 6, 1}

输出:

Common elements are: 4 5 6 7 1

方法1：

这是一种强硬的方法，简单地在第一个数组中遍历，对于第一个数组中的每一个元素，在第二个数组中遍历，找出它是否存在，如果是，则在结果数组中检查它（以避免重复），之后，如果我们发现这个元素不存在于结果数组中，则打印它并将其存储在结果数组中。

// C Program to demonstrate scrunity of
// 2 Common Array Elements Using Brute force
#include <stdio.h>
 
int main()
{
    int array1[] = { 8, 2, 3, 4, 5, 6, 7, 1 };
    int array2[] = { 4, 5, 7, 11, 6, 1 };
    int i, j, flag, x, k = 0;
    int result[100];
    printf("Common elements are: ");
   
    // To traverse in array1.
    for (i = 0; i < sizeof(array1) / 4; i++) {
       
        // To traverse in array2.
        for (j = 0; j < sizeof(array2) / 4; j++) {
           
            // To match elements of array1 with elements of
            // array2.
            if (array1[i] == array2[j]) {
               
                flag = 0;
               
                // To traverse in result array.
                for (x = 0; x < k; x++) {
                   
                    // Check whether found element is
                    // already present in result array or
                    // not.
                    if (result[x] == array1[i]) {
                        flag++;
                    }
                }
               
                // If we found a new element which is common
                // in both arrays then store it in result
                // array and print it.
                if (flag == 0) {
                   
                    result[k] = array1[i];
                    printf("%d ", result[k]);
                    k++;
                }
            }
        }
    }
}

输出

Common elements are: 4 5 6 7 1

时间复杂度。O(mnk)

Auxiliary Space: O(max(m,n))，因为在最坏的情况下，所有的元素都可能是不同的和共同的。

方法2：

这个逻辑可以应用于已排序的数组，如果没有给出已排序的数组，则使用合并排序，因为其时间复杂度较低，然后应用这种方法。

1.在一个数组中使用两个变量进行遍历，i代表数组1，j代表数组2。
2.如果数组1的元素小于数组2的元素，则检查i++。
3.检查数组2的元素是否小于数组1的元素，然后j++。
4.检查数组1的元素是否等于数组2的元素，然后检查它是否在之前被打印出来，如果没有，则打印出来并存储在结果数组中。

// C Program to demonstrate scrunity of
// 2 Common Array Elements Using Merge
// Sort and then Traversing
#include <stdio.h>
 
int main()
{
    int array1[] = { 1, 2, 2, 3, 5, 6, 7, 8, 18, 29, 37 };
    int array2[] = { 2, 2, 4, 5, 7, 9, 10, 18 };
    int i = 0, j = 0, flag, x, k = 0;
    int result[100];
   
    // Calculate size of arrays
    int array1_size = sizeof(array1) / sizeof(array1[0]);
    int array2_size = sizeof(array2) / sizeof(array2[0]);
   
    printf("Common elements are: ");
   
    // Step 1
    while (i < array1_size && j < array2_size) {
       
        // Step 2
        if (array1[i] < array2[j]) {
            i++;
        }
        // Step 3
        else if (array1[i] > array2[j]) {
            j++;
        }
        // Step 4
        else {
            flag = 0;
           
            // To traverse in result array.
            for (x = 0; x < k; x++) {
               
                // Check whether found element is already
                // present in result array or not.
                if (result[x] == array1[i]) {
                    flag++;
                }
            }
           
            // If we found a new element which is common in
            // both arrays then store it in result array and
            // print it.
            if (flag == 0) {
                printf("%d ", array1[i]);
                result[k] = array1[i];
                k++;
            }
            i++;
            j++;
        }
    }
}

输出