找出数组中的所有 K 近邻下标
难度:
标签:
题目描述
代码结果
运行时间: 27 ms, 内存: 16.3 MB
// Java Stream Solution
// 思路:
// 1. 使用 IntStream 来遍历数组,找到所有等于 key 的下标。
// 2. 对于每个找到的下标,使用嵌套的 IntStream 标记该下标前后 k 距离内的下标为 K 近邻下标。
// 3. 使用 distinct 去重,然后排序并返回结果。
import java.util.*;
import java.util.stream.*;
public class Solution {
public List<Integer> findKNearbyIndices(int[] nums, int key, int k) {
return IntStream.range(0, nums.length)
.filter(i -> nums[i] == key)
.mapToObj(i -> IntStream.rangeClosed(Math.max(0, i - k), Math.min(nums.length - 1, i + k)))
.flatMap(IntStream::boxed)
.distinct()
.sorted()
.collect(Collectors.toList());
}
}
解释
方法:
此题解采用差分数组的方法来高效地标记那些受到关键字key影响的元素范围。首先,遍历数组nums,每当找到一个值等于key的元素时,计算出这个元素对其它元素产生影响的范围,即从i-k到i+k(需要考虑边界条件,确保不超出数组界限)。在差分数组diff中,对应位置left增加1表示开始受影响,right+1减去1表示这一区域受影响结束。之后,通过一次遍历累加差分数组diff,可以得到每个位置上的受影响累积值。最后,遍历累加后的差分数组,将所有非零元素的下标(表示这些位置受到key的影响并满足条件)收集到结果中。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在确定差分数组的长度为n+10时,为什么选择加10,这个数值是否有特别的含义或者是基于什么考虑?
▷🦆
在处理边界条件时,您是如何确保不会出现数组越界的错误?具体是如何计算left和right边界的?
▷🦆
差分数组diff中每个位置的值是如何表示当前元素是否受到key影响的?能否详细解释差分数组的工作原理及其如何通过累加来表示影响区间?
▷🦆
在最后收集结果的过程中,为什么可以直接遍历diff数组而不是nums数组来确定哪些下标是K近邻下标?
▷