比较C中未排序数组值的优雅方法？

Question

我在C中有两个int数组,我想比较它们.这是我非常快速的攻击,但我想知道是否有更快的方法.

1)找到一个不在我们正在比较的数组(arr2)中的整数.
2)复制原始数组(arr2).
3)迭代第一个数组(arr1),如果在复制的数组中找到元素,我们用我们知道的原始数组中的值替换该索引处的值(这是为了防止多个时的短路)相同值的值在数组中).

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


bool isin(int arr[], int elem, size_t len, size_t *index) {
    int i;
    for (i = 0; i < len; ++i) {
        if (arr[i] == elem) {
            if(index != NULL)
                *index = i;
            return true;
        }
    }
    return false;
}

int notInArray(int arr[], size_t len) {
    int r;
    do {
        r = rand();
    } while (isin(arr, r, len, NULL));
    return r;
}

bool arraysEqual(int arr1[], int arr2[], size_t len) {
    size_t i, j, index;
    int notInArr2 = notInArray(arr2, len);

    int *arr = (int*)malloc(len * sizeof(int));

    for (i = 0; i < len; ++i)
        arr[i] = arr2[i]; /*copy arr2 to arr*/

    for (i = 0; i < len; ++i) {
        if (isin(arr, arr1[i], len, &index))
            arr[index] = notInArr2; /*replace that elemnt with something that we know is not in the original array*/
        else
            return free(arr), false;
    }
    free(arr);
    return true;
}

int main() {
    srand(time(NULL));
    int a[] = { 3, 9, 1, 3, 8 };
    int b[] = { 1, 8, 3, 3, 9 };
    printf("%i\n", arraysEqual(a, b, sizeof(a) / sizeof(int)));
    system("pause");
} 

我不一定在寻找源代码,但更多的是关于如何实现它的一般概念.

Answer 1

从算法的角度来看,您的解决方案是次优的,并且O(n^2)及时执行比较(因为isin为数组中的每个元素调用)和O(n)额外的空间(因为您分配了数组的副本).

有更便宜的方法来执行此任务,这里有5种替代方法的概述:

• 计算一个数组的哈希集或计数字典(频率分布)并迭代另一个数组以确定匹配的值 - 直方图(O(n)时间,O(n)空间)
• 与上面相同,但使用Bloom Filter,前提是您不关心匹配值频率,也不介意误报的风险(O(n)时间,O(1)空间)
• 对其中一个数组进行就地排序,并使用二进制搜索来检测匹配(O(n log n)Quicksort的时间,以及O(log n)二进制搜索的O(1)空间).
• 如果输入数组是不可变的,那么就像上面的选项一样,但是排序成一个新的数组(与上面相同的时间复杂度,但O(n)空间)
• 对两个数组进行排序并检查相同索引处的所有元素是否相等(O(2n log n)时间,O(1)空间).