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

Question

给定两个已排序的数组A和B，找到i和j，使得|A[i] - B[j]|最小。

- simplfuzz

---

有两道作业题，你必须至少自己尝试一下它们。 - H H

为什么要急于关闭？这是一个真正的问题。它不是模糊的、不完整的、过于宽泛的或修辞性的。在当前的形式下，它可以得到合理的回答。 - moinudin

@marcog：即使没有其他原因，也希望能够阻止他将一些教科书中的问题复制到SO上。 - David

@David 这个发帖人在短短的9分钟内发布了4个问题（全部已关闭）！ - Dr. belisarius

@dharm0us，“我真的必须在我的问题中发布我的答案吗？”对于家庭作业和面试问题来说，这将是一个很好的开始。 - H H

Answer 1

由于数组已经排序，因此您可以使用2个指针（每个数组一个）遍历它们。如果|A[i+1] - B[j]| < |A[i] - B[j+1]|，则增加i，否则增加j。继续进行，直到其中一个数组的末尾。在此过程中跟踪最小索引。

- moinudin

---

这段代码的最坏运行时间复杂度是多少？应该是n^2，对吧？ - Yash

O(nlogm)：对于A中的每个元素，使用二分查找方法在数组B中找到最接近该元素值的元素。 - Yash

我该如何自己找出这样的答案？你用什么方法来解决它的？ - template boy

如果|A [0] - B [0]|小于所有其他差异怎么办。也许你应该添加一个角落情况来比较数组的前两个元素，除此之外，我认为它看起来很好。 - username