c - 简单程序: checking if one array is included in another or viceversa

Question

我想创建一个简单的函数，其工作原理如下面的评论中所述:

int included(const int v1[], const int v2[], int dim1, int dim2)
{
    int i, j;
    int found;
    int amount;

    for(i = amount = 0; i < dim1; i++)
    {
        found = 0;
        for(j = 0; j < dim2 && !found; j++)
        {
            if(v1[i] == v2[j])
            {
                amount++;
                found = 1;
            }
        }
    }
    if(amount >= dim2)          /*  Returns 0 if v1's elements are      */
        return 2;               /*  not in v2, and v2's are not in v1,  */
    if(amount >= dim1)          /*  Returns 1 if v1's elements are in v2*/
        return 1;               /*  And returns 2 if v2's elements are  */
    return 0;                   /*  in v1. If both situations happen    */
}                               /*  it returns whatever (1 or 2).       */

元素的顺序并不重要，例如 v1[5]={0,1,1,1,1}, v2[2]={1,0} 应返回1 或 2。但是代码现在无法正常工作。

有什么简单的方法可以使其尽可能高效吗？ (我是c初学者)。

Answer 1

您的算法逻辑不正确:您无法通过简单的计数确定答案。

Is there any simple way to make this as efficient as possible?

让我们从正确开始，然后讨论优化。

实现该逻辑的一种方法是引入一个函数，该函数会告诉您 int a[] 中是否有任何元素。 int b[] 中缺失:

int missing(const int a[], const int b[], size_t dimA, size_t dimB) {
    // Return 1 if there exists an element of a[]
    // that is not present in b[]. Otherwise return 0.
    ...
}

现在你的included()函数可以实现如下:

int included(const int v1[], const int v2[], int dim1, int dim2) {
    int missing1in2 = missing(v1, v2, dim1, dim2);
    int missing2in1 = missing(v2, v1, dim2, dim1);
    if (missing1in2 && missing2in1) {
        // Both sets have elements outside of each other
        return 0;
    }
    return missing2in1 ? 1 : 2;
}

如果您实现missing以您的代码使用的简单方式(两个嵌套循环和一个标志；如果找到该项目，则尽早中断；如果在完成内部循环后未设置 0，则返回 found)代码复杂度为 O(n²)。

您可以通过对两个数组进行排序来加快速度，这样您就可以确定 O(n) 中是否存在缺失元素。如果您使用qsort算法，整体代码复杂度为 O(n log₂n)。

您可以通过使用 hash table 进一步简化这一过程。 。但是，C 标准库缺乏开箱即用的实现，因此您需要提出自己的或 borrow someone else's implementation 。这会将复杂性降低到 O(n)。