leetcode
leetcode 2801 ~ 2850
最小差

最小差

难度:

标签:

题目描述

Given two arrays of integers, compute the pair of values (one value in each array) with the smallest (non-negative) difference. Return the difference.

Example:

Input: {1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
Output:  3, the pair (11, 8)

Note:

  • 1 <= a.length, b.length <= 100000
  • -2147483648 <= a[i], b[i] <= 2147483647
  • The result is in the range [0, 2147483647]

代码结果

运行时间: 96 ms, 内存: 22.5 MB


/* 
题目思路:
1. 首先对两个数组进行排序。
2. 将两个数组转换为Stream。
3. 使用Stream的有序合并操作,保持最小差值。
4. 在合并过程中计算当前两数之差的绝对值,并与当前最小差值进行比较,若更小则更新。
5. 遍历结束后,返回最小差值。
*/

import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.IntStream;

public class MinDifferenceStream {
    public static int findMinDifference(int[] a, int[] b) {
        Arrays.sort(a);
        Arrays.sort(b);
        return IntStream.concat(IntStream.of(a), IntStream.of(b))
                        .boxed()
                        .sorted(Comparator.comparingInt(x -> x))
                        .reduce((x, y) -> {
                            int diff = Math.abs(x - y);
                            return diff < Math.abs(x - y) ? x : y;
                        })
                        .map(Math::abs)
                        .orElse(Integer.MAX_VALUE);
    }

    public static void main(String[] args) {
        int[] a = {1, 3, 15, 11, 2};
        int[] b = {23, 127, 235, 19, 8};
        System.out.println(findMinDifference(a, b)); // 输出3
    }
}

解释

方法:

此题解首先对两个数组进行排序,然后使用两个指针分别遍历这两个数组,比较当前指针所指的元素,以尽可能找到最小的差值。排序后的数组保证了元素是有序的,从而可以通过调整两个指针的位置来比较不同数组中的最接近的元素。指针移动的规则是:若当前a中的元素小于b中的元素,则移动指向a的指针;若b中的元素小于a中的元素,则移动指向b的指针。通过这种方式,能够高效地找到两个数组中差值最小的一对数。

时间复杂度:

O(n log n + m log m)

空间复杂度:

O(1)

代码细节讲解

🦆
排序两个数组的目的是什么?这对于双指针遍历寻找最小差值有什么具体的帮助?
排序两个数组的目的是为了将数组内的元素按照升序排列,这样在使用双指针遍历时可以有效地比较和移动指针。在有序的数组中,任意两个相邻的元素之间的差值是逐渐增大或保持的。因此,通过比较两个有序数组中的元素,可以更系统地寻找并缩小两数组元素间的最小差值。当指针指向的两个元素相差较大时,可以通过移动较小元素所在数组的指针来尝试找到更小的差值,这种方法保证了不会错过任何可能的最小差值对。
🦆
在实现中提到,当`a[i] <= b[j]`时,i指针会继续移动直到找到一个大于`b[j]`的`a[i]`。这种方法是否有可能跳过某些潜在的最小差值对?
这种方法不会跳过潜在的最小差值对。原因是在有序数组中,如果`a[i]`逐渐逼近`b[j]`,则每次`i`指针的移动都是为了寻找更接近`b[j]`的值。当`a[i]`超过`b[j]`时,已经尝试了所有可能使`a[i]`接近`b[j]`的组合。然而,当`a[i]`刚好小于`b[j]`而后一个元素又大于`b[j]`时,实际已经包括了与`b[j]`差值最小的可能性。因此,即使继续移动i指针,也不会有更小的差值存在。
🦆
代码中使用了`flag`变量来控制比较的方向,请问这种做法与直接比较`a[i]`和`b[j]`,然后决定移动哪个指针有什么不同?是否有更简洁的方法来实现这一逻辑?
使用`flag`变量的目的是为了在每次比较后控制下一次的比较方向,这样似乎可以避免重复的比较和不必要的指针移动。然而,这种方法增加了代码的复杂性和理解难度。更简洁的方法是直接在每次循环中比较`a[i]`和`b[j]`,并基于比较结果直接决定移动哪个指针。如果`a[i]`小于`b[j]`,则移动i;如果`b[j]`小于`a[i]`,则移动j。这样直接根据两元素的大小关系来移动指针,可以使逻辑更直接、代码更清晰。

相关问题