最小绝对差
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
为什么在这个问题中首先对数组进行排序是必要的?
▷🦆
在第一次遍历时你是如何确保已经找到了最小的绝对差值?
▷🦆
如果在第一次遍历中遇到多个相同的最小差值,你是如何处理这种情况的?
▷🦆
为什么在第二次遍历中只考虑相邻元素之间的差值?
▷