LintCode 387 [The Smallest Diffe

原题

给定两个整数数组（第一个是数组 A，第二个是数组 B），在数组 A 中取 A[i]，数组 B 中取 B[j]，A[i] 和 B[j]两者的差越小越好(|A[i] - B[j]|)。返回最小差。

样例
给定数组 A = [3,4,6,7]， B = [2,3,8,9]，返回 0。

解题思路

• Two Pointers
• 首先给两个数组排序
• 两个指针分别指向两个数组的起始点，每次计算difference，谁小向前移动谁

完整代码

class Solution:
    # @param A, B: Two lists of integer
    # @return: An integer
    def smallestDifference(self, A, B):
        # write your code here
        A = sorted(A)
        B = sorted(B)
        res = sys.maxint
        p1, p2 = 0, 0
        while p1 < len(A) and p2 < len(B):
            if A[p1] > B[p2]:
                res = min(res, A[p1] - B[p2])
                p2 += 1
            else:
                res = min(res, B[p2] - A[p1])
                p1 += 1
        return res