Force button topic link

Description of solution steps

  • First sort two arrays
  • Minimize the number of intervals to traverse
  • Double pointer traversal results

You can think of two arrays as two intervals on the integer number line (discrete intervals defined by the maximum and minimum of the array, but think of them as continuous intervals or line segments). By analyzing the position relationship of the two intervals, we can clarify the processing process of “reducing the interval to be traversed”.

  • There are cases where the interval boundaries are equal
  • There is no intersection between the two intervals
  • One of these two intervals completely encompasses the other
  • There’s some intersection between the two intervals

I put a lot of effort into minimizing the number of intervals to traverse. It should be emphasized that the time complexity of sorting is O(nlogn)O(nlogn)O(nlogn) O(nlogn), and the time complexity of subsequent traversal calculation results is O(n)O(n)O(n). The time is mainly spent on sorting, so “minimize the traversal interval” optimization has little effect on the overall performance improvement. I just thought it was fun to write about. Suppose you have a problem where the input two arrays (intervals) are already ordered and you want to merge the arrays (intervals), or if the merge is part of the calculation process, it makes sense to reduce the length of the array (intervals) to traverse. The reader can modify it by removing the part that reduces the traversal interval to simplify the code. See the code and comments below for details.

import "math"
import "sort"

func smallestDifference(a []int, b []int) int {
	la := len(a)
	if la == 0 {
		panic("a is empty")
	}
	lb := len(b)
	if lb == 0 {
		panic("b is empty")}// la ! = 0 && lb ! = 0
	sort.Sort(sort.IntSlice(a))
	sort.Sort(sort.IntSlice(b))

	// Let's see if we can get the result quickly

	// The endpoints are equal, 4 cases
	if a[0] == b[0] ||
		a[0] == b[lb- 1] ||
		a[la- 1] == b[0] ||
		a[la- 1] == b[lb- 1] {
		return 0
	}

	// Do not intersect, two cases
	if a[la- 1] < b[0] {
		return b[0] - a[la- 1]}if b[lb- 1] < a[0] {
		return a[0] - b[lb- 1]}// Try to narrow the traversal interval, find the maximum value less than the minimum value, find the minimum value greater than the maximum value.

	// There are two cases
	// a[0] < b[0] && b[lb-1] < a[la-1]
	// A contains b
	minDiff, ok := handleInclusion(a, b)
	if ok {
		return minDiff
	}
	// b[0] < a[0] && a[la-1] < b[lb-1]
	// b contains a
	minDiff, ok = handleInclusion(b, a)
	if ok {
		return minDiff
	}

	// Then determine the intersection (not completely included), two cases
	// a[la-1] > b[0] && a[la-1] < b[lb-1]
	// The right end of A is in b
	minDiff, ok = handleIntersection(a, b)
	if ok {
		return minDiff
	}
	// The right end of b is in A
	minDiff, ok = handleIntersection(b, a)
	if ok {
		return minDiff
	}

	/ / out
	return getMinAbsDiff(a, b)
}

// Try to handle the intersection case
func handleIntersection(a, b []int) (int.bool) {
	var (
		la = len(a)
		lb = len(b)
	)
	// intersect (not completely included)
	if a[la- 1] > b[0] && a[la- 1] < b[lb- 1] { // The right end of A is in b
		// Try to narrow the range that B traverses.
                // Find the smallest value in b greater than a[la-1].
		bRight, equal := searchMinValueGreaterThanX(b, a[la- 1])
		if equal {
			return 0.true
		}
                // Minimize the range of a to traverse.
		// Find the maximum value of a less than b[0].
		aLeft, equal := searchMaxValueSmallerThanX(a, b[0])
		if equal {
			return 0.true
		}
		return getMinAbsDiff(a[aLeft:], b[:bRight+1]), true
	}
	return 0.false
}

// Try to handle the contained case
func handleInclusion(a, b []int) (int.bool) {
	var (
		la = len(a)
		lb = len(b)
	)
	// Fully included
	if a[0] < b[0] && b[lb- 1] < a[la- 1] { // A contains b
		// Reduce the range of a to traverse
		// Find the maximum value of a less than b[0]
		aLeft, equal := searchMaxValueSmallerThanX(a, b[0])
		if equal {
			return 0.true
		}
		// Find the smallest value in a greater than b[lb-1]
		aRight, equal := searchMinValueGreaterThanX(a, b[lb- 1])
		if equal {
			return 0.true
		}
		return getMinAbsDiff(a[aLeft:aRight+1], b), true
	}
	return 0.false
}

// double pointer traversal, calculate the result
func getMinAbsDiff(a, b []int) int {
	var (
		ia      int
		ib      int
		la      = len(a)
		lb      = len(b)
		minDiff = math.MaxInt32
	)
	for ia < la && ib < lb {
		if a[ia] == b[ib] {
			return 0
		}
		if a[ia] < b[ib] {
			x := b[ib] - a[ia]
			if x < minDiff {
				minDiff = x
			}
			ia++
		} else {
			x := a[ia] - b[ib]
			if x < minDiff {
				minDiff = x
			}
			ib++
		}
	}
	return minDiff
}

// Find the maximum value less than x in the ordered array A.
// If found, return the index of that element.
// If both are greater than x, return 0.
// If the bool returned is true, a value equal to x has been found.
func searchMaxValueSmallerThanX(a []int, x int) (int.bool) {
	var (
		low int
		high = len(a)- 1
		maxVal int
		i = - 1
	)
	for low <= high {
		mid := low + (high-low)>>1
		v := a[mid]
		if v == x {
			return mid, true
		}
		if v < x {
			ifi ! =- 1 {
				if v > maxVal {
					maxVal = v
					i = mid
				}
			} else {
				maxVal = v
				i = mid
			}
			low = mid+1
		} else {
			high = mid- 1}}// Both are greater than x
	if high == - 1 {
		return low, false
	}
	return i, false
}

// Find the smallest value greater than x in the ordered array A.
// If found, return the index of that element.
// If both are smaller than x, return a maximum index.
// If the bool returned is true, a value equal to x has been found.
func searchMinValueGreaterThanX(a []int, x int) (int.bool) {
	var (
		low int
		high = len(a)- 1
		minVal int
		i = - 1
	)
	for low <= high {
		mid := low + (high-low)>>1
		v := a[mid]
		if v == x {
			return mid, true
		}
		if v < x {
			low = mid+1
		} else {
			ifi ! =- 1 {
				if v < minVal {
					minVal = v
					i = mid
				}
			} else {
				minVal = v
				i = mid
			}
			high = mid- 1}}// Both are less than x
	if low == len(a) {
		return high, false
	}
	return i, false
}
Copy the code

Sorting (assuming based on quicksort) time complexity O(nlogn)O(nlogn)O(nlogn) O(nlogn) space complexity O(logn)O(logn)O(logn) O(logn)(stack overhead). The attempt to reduce the traversal interval is based on binary search and the time complexity is O(logn)O(logn)O(logn). Time complexity O(n)O(n)O(n) O(n). Overall, time complexity O(nlogn)O(nlogn)O(nlogn) O(nlogn) space complexity O(logn)O(logn)O(logn) O(logn).