如何有效地编写代码来检查具有相同元素数量的两个数组是否具有相同的元素，即使位于不同的位置？

Question

我试图解决这个问题：给定一个数字 N 和两个包含 N 个元素的 A、B 数组，确定 B 是否包含与 A 相同的元素（不一定位于相同位置）。

将有三个输入：

• 第一行包含 N 个元素

• 第二行包含数组 A 的 N 个元素

• 第三行包含数组 B 的 N 个元素

例子：

输入：

4
4 2 3 7
2 3 4 9

输出：no

输入：

5
5 1 1 9 3
1 9 1 5 3

输出：yes

我的代码：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    scanf("%d", &n);
    long int a[n], b[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%ld", &a[i]);
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%ld", &b[i]);
    }
    
    int same;
    for (int j = 0; j < n; j++)
    {
        same = 0;
        for (int k = 0; k < n; k++)
        {
            if (a[j] == b[k])
            {
                same = 1;
            }
        }
        if (same == 0)
        {
            break;
        }
    }
    if (same == 0)
    {
        printf("no\n");
    }
    else
    {
        printf("yes\n");
    }
    return 0;
}

我的代码将获取数组 A 的第一个元素并将其与数组 B 的所有元素进行比较，然后获取 A 的以下元素并执行相同的操作。这种方法可以成功地为前 3 个测试用例提供正确的输出（问题中仅显示了 2 个），但它在测试 4 上显示了错误的答案，我不知道为什么，因为未显示该测试用例的输入。所以，请帮我找出我的代码中的问题。

Answer 1

如果数组具有相同的数字但数量不同，您的方法具有二次时间复杂度，1 1 2则不起作用：例如：即使数组并不严格包含可能不同的顺序的相同数字，1 2 2也会产生。yes

您可以使用额外的布尔数组来存储是否b[k]已被使用来避免此问题。

更有效的方法是复制两个数组，对它们进行排序并比较排序后的数组（复杂度O(N.log(N))）。

这是使用额外布尔数组的修改版本：

#include <stdio.h>
#include <stdbool.h>

int main(void)
{
    int n;

    if (scanf("%d", &n) != 1 || n <= 0)
        return 1;

    long int a[n], b[n];
    bool seen[n];

    for (int i = 0; i < n; i++) {
        if (scanf("%ld", &a[i]) != 1)
            return 1;
    }
    for (int i = 0; i < n; i++) {
        if (scanf("%ld", &b[i]) != 1)
            return 1;
        seen[i] = false;
    }
    
    int same = 1;
    for (int j = 0; j < n; j++) {
        same = 0;
        for (int k = 0; k < n; k++) {
            if (a[j] == b[k] && seen[k] == false) {
                same = 1;
                seen[k] = true;
                break;
            }
        }
        if (same == 0)
            break;
    }
    if (same == 0) {
        printf("no\n");
    } else {
        printf("yes\n");
    }
    return 0;
}

这是一个更有效的版本（对于大型集合），它使用以下方式对数组进行排序qsort：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int compare_longs(const void *aa, const void *bb) {
    const long int *a = aa;
    const long int *b = bb;
    return (*a > *b) - (*a < *b);
}

long int *read_array(int n) {
    long int *a = calloc(sizeof(*a), n);
    if (a == NULL) {
        fprintf(stderr, "cannot allocate array\n");
        exit(1);
    }
    for (int i = 0; i < n; i++) {
        if (scanf("%ld", &a[i]) != 1) {
            fprintf(stderr, "input error\n");
            free(a);
            exit(1);
        }
    }
    return a;
}

int main(void) {
    int n;

    if (scanf("%d", &n) != 1 || n <= 0)
        return 1;

    long int *a = read_array(n);
    long int *b = read_array(n);

    qsort(a, n, sizeof(*a), compare_longs);
    qsort(b, n, sizeof(*b), compare_longs);

    int same = 1;
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) {
            same = 0;
            break;
        }
    }
    if (same == 0) {
        printf("no\n");
    } else {
        printf("yes\n");
    }
    free(a);
    free(b);
    return 0;
}

最后，这是使用哈希表的替代方案，它应该具有准线性时间复杂度，但需要额外的内存：

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

enum hash_state { FREE = 0, USED, DELETED };

typedef struct hash_entry {
    long int key;
    enum hash_state state;
    int count;
} hash_entry;

typedef struct hash_table {
    size_t size;
    hash_entry *arr;
} hash_table;

size_t hash_hash(hash_table *tab, long int key) {
    unsigned long int v = key;
    // rotate left one bit
    v = (v << 1) | (v / (ULONG_MAX ^ (ULONG_MAX >> 1)));
    return v % tab->size;
}

hash_table *hash_init(hash_table *tab, size_t n) {
    if (n > SIZE_MAX / 2)
        return NULL;
    tab->size = (n * 2) | 1;
    tab->arr = calloc(tab->size, sizeof(hash_entry));
    if (!tab->arr)
        return NULL;
    return tab;
}

void hash_free(hash_table *tab) {
    free(tab->arr);
}

hash_entry *hash_add(hash_table *tab, long int key) {
    for (size_t i = hash_hash(tab, key);; i = (i + 1) % tab->size) {
        if (tab->arr[i].state == FREE) {
            tab->arr[i].state = USED;
            tab->arr[i].key = key;
            return &tab->arr[i];
        }
        if (tab->arr[i].state == USED && tab->arr[i].key == key) {
            return &tab->arr[i];
        }
    }
}

hash_entry *hash_find(hash_table *tab, long int key) {
    for (size_t i = hash_hash(tab, key);; i = (i + 1) % tab->size) {
        if (tab->arr[i].state == FREE)
            return NULL;
        if (tab->arr[i].state == USED && tab->arr[i].key == key)
            return &tab->arr[i];
    }
}

long int *read_array(size_t n) {
    long int *a = calloc(sizeof(*a), n);
    if (a == NULL) {
        fprintf(stderr, "cannot allocate arrays\n");
        exit(1);
    }
    for (size_t i = 0; i < n; i++) {
        if (scanf("%ld", &a[i]) != 1) {
            fprintf(stderr, "input error\n");
            free(a);
            exit(1);
        }
    }
    return a;
}

int main(void) {
    int n;

    if (scanf("%d", &n) != 1 || n <= 0)
        return 1;

    long int *a = read_array(n);
    long int *b = read_array(n);

    hash_table tab[1];
    if (!hash_init(tab, n)) {
        fprintf(stderr, "cannot initialize hash table\n");
        return 1;
    }
    for (int i = 0; i < n; i++) {
        hash_add(tab, a[i])->count++;
    }
    int same = 1;
    for (int i = 0; i < n; i++) {
        hash_entry *e = hash_find(tab, b[i]);
        if (!e || !e->count--) {
            same = 0;
            break;
        }
    }
    hash_free(tab);
    if (same == 0) {
        printf("no\n");
    } else {
        printf("yes\n");
    }
    free(a);
    free(b);
    return 0;
}

实际上，该hash版本仅比大型随机集（100k 或 100 万个随机值）的版本稍快，qsort因为散列的开销很大，散列函数很简单并且排序中的对数因子很小。

这是 100000 个随机数（和一个打乱数组）的基准：

#include <stdio.h>
#include <stdbool.h>

int main(void)
{
    int n;

    if (scanf("%d", &n) != 1 || n <= 0)
        return 1;

    long int a[n], b[n];
    bool seen[n];

    for (int i = 0; i < n; i++) {
        if (scanf("%ld", &a[i]) != 1)
            return 1;
    }
    for (int i = 0; i < n; i++) {
        if (scanf("%ld", &b[i]) != 1)
            return 1;
        seen[i] = false;
    }
    
    int same = 1;
    for (int j = 0; j < n; j++) {
        same = 0;
        for (int k = 0; k < n; k++) {
            if (a[j] == b[k] && seen[k] == false) {
                same = 1;
                seen[k] = true;
                break;
            }
        }
        if (same == 0)
            break;
    }
    if (same == 0) {
        printf("no\n");
    } else {
        printf("yes\n");
    }
    return 0;
}