Question

面试题 16.06. 最小差

English Version

题目描述

给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差

示例：

输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
输出： 3，即数值对(11, 8)

提示：

• 1 <= a.length, b.length <= 100000
• -2147483648 <= a[i], b[i] <= 2147483647
• 正确结果在区间[-2147483648, 2147483647]内

解法

方法一：排序 + 二分查找

我们可以对数组 $b$ 进行排序，并对数组 $a$ 中的每个元素 $x$ 在数组 $b$ 中进行二分查找，找到最接近 $x$ 的元素 $y$，那么 $x$ 和 $y$ 的差的绝对值就是 $x$ 和 $b$ 中最接近 $x$ 的元素的差的绝对值。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组 $b$ 的长度。

class Solution:
  def smallestDifference(self, a: List[int], b: List[int]) -> int:
    b.sort()
    ans = inf
    n = len(b)
    for x in a:
      j = bisect_left(b, x)
      if j < n:
        ans = min(ans, b[j] - x)
      if j:
        ans = min(ans, x - b[j - 1])
    return ans

class Solution {
  public int smallestDifference(int[] a, int[] b) {
    Arrays.sort(b);
    long ans = Long.MAX_VALUE;
    for (int x : a) {
      int j = search(b, x);
      if (j < b.length) {
        ans = Math.min(ans, (long) b[j] - x);
      }
      if (j > 0) {
        ans = Math.min(ans, (long) x - b[j - 1]);
      }
    }
    return (int) ans;
  }

  private int search(int[] nums, int x) {
    int l = 0, r = nums.length;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

class Solution {
public:
  int smallestDifference(vector<int>& a, vector<int>& b) {
    sort(b.begin(), b.end());
    long long ans = LONG_LONG_MAX;
    for (int x : a) {
      auto it = lower_bound(b.begin(), b.end(), x);
      if (it != b.end()) {
        ans = min(ans, (long long) *it - x);
      }
      if (it != b.begin()) {
        ans = min(ans, x - (long long) *prev(it));
      }
    }
    return ans;
  }
};

func smallestDifference(a []int, b []int) int {
  sort.Ints(b)
  var ans int = 1e18
  for _, x := range a {
    i := sort.SearchInts(b, x)
    if i < len(b) {
      ans = min(ans, b[i]-x)
    }
    if i > 0 {
      ans = min(ans, x-b[i-1])
    }
  }
  return ans
}

function smallestDifference(a: number[], b: number[]): number {
  b.sort((a, b) => a - b);
  let ans = Infinity;
  const search = (nums: number[], x: number): number => {
    let [l, r] = [0, nums.length];
    while (l < r) {
      const mid = (l + r) >> 1;
      if (nums[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };
  for (const x of a) {
    const j = search(b, x);
    if (j < b.length) {
      ans = Math.min(ans, b[j] - x);
    }
    if (j > 0) {
      ans = Math.min(ans, x - b[j - 1]);
    }
  }
  return ans;
}

方法二：排序 + 双指针

我们可以对数组 $a$ 和 $b$ 分别进行排序，然后使用双指针的方法，维护两个指针 $i$ 和 $j$，初始时分别指向数组 $a$ 和 $b$ 的起始位置。每一次，我们计算 $a[i]$ 和 $b[j]$ 的差的绝对值，并且更新答案。如果 $a[i]$ 和 $b[j]$ 指向的两个元素中的一个元素比另一个元素要小，则将指向较小元素的指针向前移动一步。当至少有一个指针超出数组范围时，遍历结束。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组 $a$ 和 $b$ 的长度。

class Solution:
  def smallestDifference(self, a: List[int], b: List[int]) -> int:
    a.sort()
    b.sort()
    i = j = 0
    ans = inf
    while i < len(a) and j < len(b):
      ans = min(ans, abs(a[i] - b[j]))
      if a[i] < b[j]:
        i += 1
      else:
        j += 1
    return ans

class Solution {
  public int smallestDifference(int[] a, int[] b) {
    Arrays.sort(a);
    Arrays.sort(b);
    int i = 0, j = 0;
    long ans = Long.MAX_VALUE;
    while (i < a.length && j < b.length) {
      ans = Math.min(ans, Math.abs((long) a[i] - (long) b[j]));
      if (a[i] < b[j]) {
        ++i;
      } else {
        ++j;
      }
    }
    return (int) ans;
  }
}

class Solution {
public:
  int smallestDifference(vector<int>& a, vector<int>& b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int i = 0, j = 0;
    long long ans = LONG_LONG_MAX;
    while (i < a.size() && j < b.size()) {
      ans = min(ans, abs(1LL * a[i] - 1LL * b[j]));
      if (a[i] < b[j]) {
        ++i;
      } else {
        ++j;
      }
    }
    return ans;
  }
};

func smallestDifference(a []int, b []int) int {
  sort.Ints(a)
  sort.Ints(b)
  i, j := 0, 0
  var ans int = 1e18
  for i < len(a) && j < len(b) {
    ans = min(ans, abs(a[i]-b[j]))
    if a[i] < b[j] {
      i++
    } else {
      j++
    }
  }
  return ans
}

func abs(a int) int {
  if a < 0 {
    return -a
  }
  return a
}

function smallestDifference(a: number[], b: number[]): number {
  a.sort((a, b) => a - b);
  b.sort((a, b) => a - b);
  let [i, j] = [0, 0];
  let ans = Infinity;
  while (i < a.length && j < b.length) {
    ans = Math.min(ans, Math.abs(a[i] - b[j]));
    if (a[i] < b[j]) {
      ++i;
    } else {
      ++j;
    }
  }
  return ans;
}