arrays - 描述一个 O(n log n) 算法来确定 A 的所有元素是否不同

Question

假设我们有两个整数数组 A 和 B，每个数组都有 n 个元素。

描述一个 O(n log n) 算法来确定 A 的所有元素是否不同

你会怎么做这个问题？我很坚持这一点。我知道我们必须做一些排序，这在某种程度上类似于二进制搜索。有任何想法吗？

Answer 1

首先，你对 和 进行排序A，如果你选择好排序算法B，你会在这部分得到复杂性。O(n log(n))

然后，您使用两个数组都已排序的事实将 A 的每个元素与 B 的每个元素进行比较。这是 的值的索引 和 的值的索引的i算法。[1, n]Aj[1, n]B

i = 1
j = 1
while i <= N and j <= N do
  if (A[i] == B[j])
    return false;
  else if (A[i] < B[j])
    i += 1
  else // A[i] > B[j]
    j += 1
end
return true;

这部分的复杂度为 O(n)，因此总体复杂度为 O(n log(n))。

Answer 2

我想你的意思是来自 B 的 A diif 的所有元素。在这种情况下：

使用 MergeSort - 对 A 进行排序 (O(nlogn) 使用 MergeSOrt 对 B 进行排序 (Onlogn)

private bool CheckIfEqual()     ///O(n)
{
for (int i=0;i<A.Count;i++)  //A.count=B.Count otherwise there are for sure not Equal
{
         if (a[i]!=b[i]
       return false
}
return true;
}

所以你有 O(nlogn)+O(nlogn)+O(n)=O(nlogn)