C&C++   发布时间:2022-04-03  发布网站:大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了比较C中未排序数组值的优雅方法?大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
我在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],&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,9 };
    printf("%i\n",arraysEqual(a,b,sizeof(a) / sizeof(int)));
    system("pause");
}

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

解决方法

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

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

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

大佬总结

以上是大佬教程为你收集整理的比较C中未排序数组值的优雅方法?全部内容,希望文章能够帮你解决比较C中未排序数组值的优雅方法?所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。