如何检查两个数组是否在 C 中具有相同的数字集？

Question

我想检查两个整型数组是否有相同的数字集。例如，如果数组 1 是 5 1 2 3 3 4 6 1，而数组 2 是 1 2 3 4 5 6，则程序 returns 1。如果任一数组中的任何数字不在第二个数组中，则程序 returns一个0.

我试过这样做，但我无法让它工作：

#include <stdio.h>

int main()
{
    int i, j, a[8]={5, 1, 2, 3, 3, 4, 6, 1}, b[6]={1, 2, 3, 4, 5, 6}, x=0;
    for(i=0; i<6; i++)
    {
        for(j=0; j<8; j++)
        {
            if(a[j]==b[i])
            {
                x=1;
                continue;
            }
            else
            {
                x=0;
                break;
            }
        }
    }
    return x;
}

编辑：谢谢Some programmer dude

#include <stdio.h>

void sort(int arr[], int n)
{
    int i, j, a;
    for (i=0; i<n; i++)
    {
        for (j=i+1; j<n; j++)
        {
            if (arr[i]>arr[j])
            {
                a=arr[i];
                arr[i]=arr[j];
                arr[j]=a;
            }
        }
    }
}

int main()
{
    int i, j, k;
    int a[8]={5, 1, 2, 3, 3, 4, 6, 1};
    int b[6]={1, 2, 3, 4, 5, 6};
    int na=8, nb=6;

    for(i=0; i<na; i++) // removing duplicates from a
    {
        for(j=i+1; j<na; j++)
        {
            if(a[i]==a[j])
            {
                for(k=j; k<na; k++)
                {
                    a[k]=a[k+1];
                }
                na--;
                j--;
            }
        }
    }

    for(i=0; i<nb; i++) // removing duplicates from b
    {
        for(j=i+1; j<nb; j++)
        {
            if(b[i]==b[j])
            {
                for(k=j; k<nb; k++)
                {
                    b[k]=b[k+1];
                }
                nb--;
                j--;
            }
        }
    }

    sort(a, na);
    sort(b, nb);

    if(na!=nb)
        return 0;

    for(i=0; i<na; i++)
    {
        if(a[i]!=b[i])
            return 0;
    }

    return 1;
}

Answer 1

你有几种方法可以解决这个问题，你可以使用两组嵌套循环交换你在两个数组上循环的顺序，以验证每个元素是否在另一个数组中找到。需要两套完整的嵌套循环，因为您有 50/50 的机会将任何一个异常值包含在任一数组中。这是蛮力法，具有潜在的最坏情况迭代次数。

因为离群值是驱动需要将一个数组作为外部循环而将另一个数组作为内部循环然后交换重复项的原因，例如捕获 5, 1, 2, 3, 3, 4, 6, 1 和 1, 2, 3, 4, 5, 6, 7，如果您可以使用另一种需要更少迭代的方法捕获异常值，则可以使您的算法更高效。

在比较每个数组的min和max时会检测到离群点，找到min和max只需要一次线性遍历每个阵列。比所有元素的最坏情况嵌套循环要好得多。

min 和 max 检查提供了一种缩短工作的方法，但如果此时结果尚无定论，则不能消除使用第二组嵌套循环向前推进的需要.为什么？考虑以下集合，其中 min 和 max 相等，但范围内的一个元素不包含在两个数组中，例如：

    int a[] = { 5, 1, 2, 3, 3, 4, 6, 112 },
        b[] = { 1, 2, 3, 4, 5, 6, 7, 112 };

检测 7 的唯一方法是通过嵌套循环，其中包含 7 的数组作为外循环。

因此您可以编写一个简短的函数来测试公共集：

#include <stdio.h>
#include <limits.h>

int commonset (int *a, int *b, int sza, int szb)
{
    int maxa = INT_MIN, maxb = INT_MIN,
        mina = INT_MAX, minb = INT_MAX;
    
    for (int i = 0; i < sza; i++) {     /* find max/min of elements of a */
        if (a[i] > maxa)
            maxa = a[i];
        if (a[i] < mina)
            mina = a[i];
    }
    for (int i = 0; i < szb; i++) {     /* find max/min of elements of b */
        if (b[i] > maxb)
            maxb = b[i];
        if (b[i] < minb)
            minb = b[i];
    }
    
    if (maxa != maxb || mina != minb)   /* validate max & mins equal or return 0 */
        return 0;
    
    for (int i = 0; i < sza; i++) {     /* compare of each element between arrays */
        int found = 0;
        for (int j = 0; j < szb; j++)
            if (a[i] == b[j]) {
                found = 1;
                break;
            }
        if (!found)
            return 0;
    }
    
    for (int i = 0; i < szb; i++) {     /* compare of each element between arrays */
        int found = 0;
        for (int j = 0; j < sza; j++)
            if (a[j] == b[i]) {
                found = 1;
                break;
            }
        if (!found)
            return 0;
    }
    
    return 1;
}

添加一个简短的示例程序：

int main (void) {
    
    int a[] = { 5, 1, 2, 3, 3, 4, 6, 1 },
        sza = sizeof a / sizeof *a,
        b[] = { 1, 2, 3, 4, 5, 6 },
        szb = sizeof b / sizeof *b,
        result;
    
    result = commonset (a, b, sza, szb);
    if (result)
        puts ("arrays have common set of numbers");
    else
        puts ("arrays have no common set of numbers");
    
    return result;
}

示例Use/Output

$ ./bin/arr_commonset
arrays have common set of numbers
$ echo $?
1

与b[] = { 1, 2, 3, 4, 5, 6, 7 }:

$ ./bin/arr_commonset
arrays have no common set of numbers
$ echo $?
0

与 a[] = { 5, 1, 2, 3, 3, 4, 6, 112 } 和 b[] = { 1, 2, 3, 4, 5, 6, 7, 112 }:

$ ./bin/arr_commonset
arrays have no common set of numbers
$ echo $?
0

甚至可能有一些方法可以将两者结合起来并减少几次迭代，而且，如果你的输入集有一个保证范围，你可以使用一个简单的频率数组 对于每个，然后需要两次简单的线性迭代来增加与数组中每个值的索引相对应的元素，然后在两个频率数组上进行第三次线性迭代，比较类似的索引要么都是非零，要么都是为零以确认公共集 -- 留给您。

检查一下，如果您有任何其他问题，请告诉我。

如何检查两个数组是否在 C 中具有相同的数字集？

How to check if two arrays have the same set of digits in C?

arrays

c

set

digits