arrays - 给定两个数组 A 和 Q，对于 Q 的每个元素，找到 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 的每个元素进行二分查找以找到最小的差，O(AlogA + QlogA)
3. 对A和Q进行排序，然后我们在每个数组上有两个指针来查找差异，O(AlogA + QlogQ)

我没有想到的最优方案是什么？

Answer 1

采访的重点可能是细节。 A 和 Q 具有不同的长度。

所以如果 A 有 16 个元素而 Q 有 1 个元素，那么你的解决方案 2 可能不是最优的。

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

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

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