leetcode
leetcode 1101 ~ 1150
最小绝对差

最小绝对差

难度:

标签:

题目描述

代码结果

运行时间: 79 ms, 内存: 27.8 MB


// Solution using Java Stream
// 思路:
// 1. 使用流对数组进行排序并找到最小绝对差。
// 2. 使用流收集所有差值等于最小绝对差的元素对。

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class MinimumAbsoluteDifferenceStream {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        // 对数组进行排序
        int[] sortedArr = Arrays.stream(arr).sorted().toArray();
        // 找到最小绝对差
        int minDiff = IntStream.range(1, sortedArr.length)
                .map(i -> sortedArr[i] - sortedArr[i - 1])
                .min().orElse(Integer.MAX_VALUE);
        // 收集所有差值等于最小绝对差的元素对
        return IntStream.range(1, sortedArr.length)
                .filter(i -> sortedArr[i] - sortedArr[i - 1] == minDiff)
                .mapToObj(i -> Arrays.asList(sortedArr[i - 1], sortedArr[i]))
                .collect(Collectors.toList());
    }
}

解释

方法:

该题解通过先对输入数组进行排序,然后使用两次遍历的方法找出所有最小绝对差的元素对。首先,通过第一次遍历计算并记录最小的差值。在第二次遍历中,查找并收集所有具有这个最小差值的元素对。因为数组已经排序,相邻元素的差值即为候选的最小绝对差。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在这个问题中首先对数组进行排序是必要的?
在这个问题中,首先对数组进行排序是必要的,因为排序后数组中的元素按从小到大的顺序排列。这样,最小的绝对差值只会出现在相邻元素之间,因为非相邻元素之间的差值会因为中间元素的存在而变大。因此,排序简化了问题,使我们只需要检查相邻元素之间的差值来找出最小绝对差。
🦆
在第一次遍历时你是如何确保已经找到了最小的绝对差值?
在第一次遍历中,通过遍历排序后的数组的相邻元素并计算它们之间的差值,可以确保找到最小的绝对差值。由于数组是有序的,最小差值一定会出现在某对相邻元素之间。初始化一个变量`min_diff`为正无穷大,然后对每一对相邻元素计算差值,如果发现更小的差值,就更新`min_diff`。这样一次遍历后,`min_diff`中存储的就是所有相邻元素差值中的最小值。
🦆
如果在第一次遍历中遇到多个相同的最小差值,你是如何处理这种情况的?
在第一个遍历中,如果遇到多个相同的最小差值,处理方式很简单。由于在寻找最小差值的过程中,只需要更新并记录最小差值`min_diff`,并不需要在此时就决定哪些元素对会被收集。所以,即使存在多个相同的最小差值,只需确保`min_diff`记录了这个值。具体哪些元素对具有这个最小差值,则留待第二次遍历时根据实际差值与`min_diff`相比较来收集。
🦆
为什么在第二次遍历中只考虑相邻元素之间的差值?
在第二次遍历中只考虑相邻元素之间的差值是因为数组已经被排序。在有序数组中,最小的绝对差值只可能出现在相邻元素之间,因为任何非相邻元素的差值必定大于或等于它们之间任何相邻元素的差值。因此,只需要检查相邻元素之间的差值是否等于第一次遍历中找到的最小差值`min_diff`,然后收集这些具有最小差值的元素对。

相关问题