给定两个数组A和Q，对于Q中的每个元素，找到A中差值最小的元素。

Question

给定两个数组A和Q，对于Q中的每个元素，找到A中差值最小的元素。

8

给定两个长度不同的未排序数组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. 暴力法：对于每个A，对于每个Q计算差异，时间复杂度为O（A * Q）。 2. 对数组A进行排序，对于每个Q元素，执行二分查找以找到最小差异，时间复杂度为O（AlogA + QlogA）。 3. 对数组A和Q进行排序，然后我们在每个数组上有两个指针来查找差异，时间复杂度为O（AlogA + QlogQ）。

有没有更优化的解决方案呢？

- Saldeho

对于您的第三种方法，时间复杂度为O(max(A log A, Q log Q))。 - Pham Trung

3

就时间复杂度而言，你的第二和第三种方法是最优的解决方案，没有比它们更优的解决方案。 - User_Targaryen

3个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SaiBot · Answer 1

我有一个基于Quickselect的想法草图，适用于|Q|<|A|的情况。这个想法是，在处理Q中的元素时，通过搜索A中差异最小的元素来对A进行部分排序。

因此，对于Q中的第一个元素，您执行类似快速选择的搜索，以找到具有最小差异的元素。这个搜索将花费O(A)，但会部分排序Q中的元素。Q中的第二个元素将从第一次搜索中受益，并进一步对A进行排序。

我目前不确定如何计算运行时间复杂度，但它可能比O(A log A)更好，因为在处理完Q中的所有元素后，A不一定完全排序。在最优情况下，它可能是O(Q log A)。

不确定是否有帮助，但也许有人可以找出缺失的部分。

- Viktor Vlasenko · Answer 2

面试中的关键可能在于细节。A和Q的长度不同。

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

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

您的解决方案2看起来很优秀，但应该重新表述。

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

- Gijs Den Hollander · Answer 3

以下方法可能更快，这取决于数组中的数据。但是假设您有以下两个数组。

A = {1、2、5、11、13} 和 Q = {3、5、12}

创建两个新数组，并填充数组，以使旧数组中的值是新数组中的索引。因此，新数组的大小是旧数组中最大的数字，重复的值将被忽略。例如：

下面是它应该如何工作的示例（伪代码）：

A'=null
Q'=null

A' and Q' have the size of the largest number in A or Q
for i < length(A) i++ {
   A'[A[i]]=A[i]
   B'[B[i]]=B[i]
} 

A'= {1,2,null,null,5,null,....,null,11,null,13}
Q'= {null,null,3,null,5,null,....,12,null}

for i < length(A') i++ {
    if(A[i] == Q[i]){ 
       print(A[i])
    } else if (A[i] == null) {
       for(j=1 j < length(A') j++) {
          if(Q[i+j] != null || Q[i-j] != null){ //here you have to be carfull nto go to -negative indices
              print[Q[i-j],Q[i+j],A[i]]
              Break;
          }
       }
    }

}

然后比较两个数组，看值的索引是否已填充。如果没有填充，请找到下一个已填充的索引。

此方法的速度取决于两个数组中数字的稀疏程度。如果您有非常大的数字（且相距很远），则这可能非常低效。

此算法的最佳情况是O（A + Q），最坏情况是O（无穷大）。