查找两个数组之间的最小差异

给定两个排序的数组A，B，找到i，j，其中| A [i] -B [j] |是最小的。查找两个数组之间的最小差异

2010-12-10 dharm0us

请说出你想知道的问题！ – 2010-12-10 18:45:10

给出2个作业题，你必须......至少自己试试。 – 2010-12-10 18:46:57

他想知道找到两个不同阵列中任何两个项目之间最小距离的最有效方法。 – sethvargo 2010-12-10 18:47:03

由于数组是排序的，所以可以用2个指针（每个数组一个）传递它们。如果|A[i+1] - B[j]| < |A[i] - B[j+1]|然后增加i，否则增量j。继续，直到您到达其中一个数组的末尾。随时跟踪最小指标。

2010-12-10 18:48:13 marcog

此代码的最坏情况运行时复杂度是多少？它应该是n^2，不是？ – Yashasvi 2014-01-27 05:42:44

O（nlogm）：对于A中的每个元素，使用二进制搜索方法来找到数组B中最接近的元素。 – Yashasvi 2014-01-27 05:45:54

如何自己找出这样的答案？你用什么方法解决它？ – 2014-11-19 22:07:38

回答