Leetcode interview questions 16.06. Minimum difference

Leetcode interview questions 16.06. Minimum difference

Links to Likou Questions

Solution step description

  • Sort the two arrays first
  • Minimize the interval to be traversed
  • Double pointer traversal calculation result

You can think of two arrays as two intervals on the integer number axis (each is a discrete interval defined by the maximum and minimum of the array, but you can think of them as continuous intervals or line segments). By analyzing the positional relationship between these two intervals, the process of "reducing the interval to be traversed" can be clarified.

  • There are cases where the boundaries of the intervals are equal
  • There is no intersection between the two intervals
  • One of the two intervals completely contains the other
  • Two intervals have a partial intersection

For this question, I spent a lot of effort on "minimize the interval to be traversed as much as possible" . It should be emphasized that the time complexity of sorting isO(nlogn)O(nlogn) , the time complexity of the subsequent traversal calculation result isO(n)O(n) , time is mainly spent on sorting, so the optimization of "minimize the interval to be traversed as much as possible" has little effect on the overall performance improvement. I just find it interesting, just write and read. Assuming that there is such a problem, the two input arrays (intervals) are already in order, and the arrays (intervals) are required to be merged, or the merge is part of the calculation process. At this time, it makes sense to reduce the length of the arrays (intervals) to be traversed. .
Readers can modify it by themselves and remove the part that reduces the traversal interval to simplify the code. For details, please see the code and comments below.

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 results quickly //End points 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 } //disjoint, 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 ] } //Next, try to narrow the traversal interval, find the maximum value smaller than the minimum value, and find the minimum value larger than the maximum value. //First judge the complete inclusion, in 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 judge 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 } // Bottom of the pocket return getMinAbsDiff(a, b) } //Try to handle the case of intersection 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 point of b The interval to traverse. //Find the smallest value in b that is greater than a[la-1]. bRight, equal := searchMinValueGreaterThanX(b, a[la -1 ]) if equal { return 0 , true } //Try to narrow the range of a to be traversed. //Find the maximum value in a that is smaller 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 included case func handleInclusion (a, b [] int ) ( int , bool ) { var ( la = len (a) lb = len (b) ) //Fully contain if a[ 0 ] <b[ 0 ] && b[lb -1 ] <a[la -1 ] { //a contains b //Reduce the range of a to be traversed //Find the ratio in a b[0] Small maximum aLeft, equal := searchMaxValueSmallerThanX(a, b[ 0 ]) if equal { return 0 , true } //Find the smallest value in a that is 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, calculation 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 largest value smaller 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 in the return value is true, it means that 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 { if i != -1 { if v> maxVal { maxVal = v i = mid } } else { maxVal = v i = mid } low = mid+ 1 } else { high = mid -1 } } //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 the largest index of a. //If the bool in the return value is true, it means that a value equal to x is 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 { if i != -1 { if v <minVal { minVal = v i = mid } } else { minVal = v i = mid } high = mid -1 } } //Both are smaller than x if low == len (a) { return high, false } return i, false } Copy code

Sorting (assuming quick sort based) time complexityO(nlogn)O(nlogn) , space complexityO(logn)O(logn) (system stack overhead).
The operation to try to reduce the traversal interval is based on binary search, and the time complexity isO(logn)O(logn) .
Time complexity of traversing calculation resultsO(n)O(n) .
Overall, the time complexityO(nlogn)O(nlogn) , space complexityO(logn)O(logn) .