The Smallest Difference Show result

Question

Given two array of integers(the first array is array A, the second array is array B), now we are going to find a element in array A which is A[i], and another element in array B which is B[j], so that the difference between A[i]`` andB[j] (|A[i] - B[j]|)`` is as small as possible, return their smallest difference.

Example For example, given array A = [3,6,7,4], B = [2,8,9,3], return 0

Thoughts

典型的two pointer题目

Solution

class Solution:
    # @param A, B: Two lists of integer
    # @return: An integer
    def smallestDifference(self, A, B):
        # write your code here
        if not A or not B:
            return 0

        A.sort()
        B.sort()
        index1 = 0
        index2 = 0
        result = sys.maxint
        while index1 < len(A) and index2 < len(B):
            diff = abs(A[index1] - B[index2])
            if diff < result:
                result = diff
            if A[index1] > B[index2]:
                index2 += 1
            else:
                index1 += 1

        while index1 < len(A):
            diff = abs(A[index1] - B[-1])
            if diff < result:
                result = diff
            index1 += 1

        while index2 < len(B):
            diff = abs(A[-1] - B[index2])
            if diff < result:
                result = diff
            index2 += 1

        return result