关于查找两个元素数组之间的最小差异的困惑

Question

我看到一个帖子 Find the minimum difference between two arrays
并使用这个概念我试图解决 SPOJ 的问题 - http://www.spoj.pl/problems/ACPC11B但奇怪的是我得到了 WA(错误答案)!!!!

然后我尝试了简单的方法..
使用两个 for 循环..
计算每个元素之间的差异...
然后我得到了空调。 !!!

谁能告诉我为什么用这个方法
if (|A[i+1] - B[j]| < |A[i] - B[j+1]|) 则递增 i，否则在这种情况下递增 j 失败????

编辑:我忘了提及，当我实现第一个方法时，我已经对两个数组执行了 qsort...
同样在SPOJ问题中，不需要差异最小的元素的索引。只需要最小的差异!!!

Answer 1

第一个链接中的方法仅在两个数组均已排序时才有效。 SPOJ 问题涉及未排序的数组。这就是为什么该方法不起作用。如果对数组进行排序，则可以应用第一种方法，但随后您需要跟踪原始索引(即排序前每个值的位置)。这可以通过将每个值转换为(值，索引)对然后对这些对进行排序来实现。这样，您将获得 O(m log m + n log n) 解决方案，而不是暴力(但正确)O(mn) 解决方案(其中 m 和 n 是数组长度)。

编辑根据您发布的代码，我有不同的答案。你的循环条件是错误的。例如，如果 i == (x - 1) 但 j != (y - 1)，则循环将执行，并且您将比较 a[ x] 到 b[j]。这是 a 的非法下标。另外，这是否应该读取与 SPOJ 中描述的相同的输入？我不知道您在哪里阅读测试用例的数量。