在O（N * log（N））时间比较两个不同大小的int数组？

Question

我需要比较两个不同大小的int数组。

它必须是最高效的。

是否可以在O（N * log（N））时间内做？

它应该打印两个数组之间不同的整数。

Answer 1

算法是O（n），但您假定数组大小相同，每个数组的大小为ARY_SIZE。

我不会为你解决整个作业，但是我建议你从下面的函数头开始：int compar2arr(int arrA[], int arrA_size, int arrB[], int arrB_size)。

请记住，对于函数参数int arrA[]仅等价于int* arrA。如基思和塞巴斯蒂安所指出的，arrA_size != arrB_size意味着不同（除非任务的作者以其他方式定义它）。所以你在开始时检查并返回false如果它成立。

编辑

好吧，我重新看了你的帖子，似乎你只是需要显示所有不等于元素，你不知道如何处理这样的事实，他们是不同的尺寸。

因此，我建议先从以下内容：

int compar2arr(int arrA[], int arrA_size, int arrB[], int arrB_size) 
{ 
    int smaller_size = // arrA_size or arrB size, the smaller one; 
    int higher_size = // arrA_size or arrB size, the higher one; 
    int *bigger_array; 
    int i;  
    int result = true; 

    if (arrA_size > arrB_size) 
     bigger_array = arrA; 
    else 
     bigger_array = arrB; 

    for (i = 0; i < smaller_size; i++) 
    { 
     if (/* i-th elements are not(!!) equal */) 
     { 
     result = false; 
     // print the values to be different 
     } 
    } 

    if (smaller_size != higher_size) 
    result = false; 

    for (i = smaller_size; i < higher_size; i++) 
    { 
     // print bigger_array[i] 
    } 

    return result; 
} 

我相信你能拿出实际的代码替换注释。 这不是最简洁的书写方式，而是想让它易于理解。无论如何，计算复杂度是O（n），尽可能好。

Answer 2

如果两个数组的大小不同，则它们已经不同，不需要比较内容，只是大小。

Answer 3

如果您只需要打印不同的元素，则在0（n）时间内不可能。解决问题的最好方法是对两个数组进行排序（使用qsort），然后从零循环到两个数组大小中较小的一个。

此外，如果您尝试打印所有不匹配的整数，则在达到第一个不同的整数时无法中断。你想要做的是在每次找到不匹配的元素时打印出“％d在％d处与％d不匹配”或类似的东西。

最后，如果大小不相等，我会遍历较长数组的最后一部分并打印出额外的元素。