给定两个数组A和Q,Q的foreach元素,找到A中具有最小差异的元素

Question

给出2个不同长度的未排序阵列A和Q. 对于Q中的每个元素,在A中找到具有最小差异的元素.

int[] findSmallestDifference(int A[], int Q[]){
   int []result = new int[Q.length];
   // insert code to find difference for each Q
   return result;
}

我在一次采访中遇到了这个问题,我提供了一些解决方案,但有人提到它还不是最优的.

解决方案我提供:

1. 蛮力:foreach A,foreach Q计算差异,O(A*Q)
2. 排序数组A,Q的foreach元素,执行二进制搜索以找到最小差异,O(AlogA + QlogA)
3. 对A和Q进行排序,然后我们在每个数组上有两个指针来查找差异,O(AlogA + QlogQ)

我没有想到的最佳解决方案是什么？

Answer 1

面试的亮点可能在于细节。A 和 Q 的长度不同。

因此，如果 A 有 16 个元素而 Q 有 1 个元素，那么您的解决方案 2 可能不是最佳的。

最佳解决方案是使用良好的排序算法（例如合并排序）对较小的数组进行排序，该算法的最坏情况复杂度为，O(NlogN)然后扫描较大的数组并通过二进制排序在较小的数组中找到最接近的元素。

您的解决方案 2 看起来是最佳的，但应该重新措辞。

• 设置 S = 较小的数组，B = 较大的数组。对数组S进行排序，对于B的每个元素，执行二分查找找到最小差异，O(SlogS + BlogS)