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

Question

<分区>

Answer 1

算法为 O(n)，但您假设数组大小相同且每个数组的大小为 ARY_SIZE。

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

请记住，对于函数参数，int arrA[] 仅等同于 int* arrA。

正如 Keith 和 Sebastian 所指出的，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)，最好。