leetcode
leetcode 1951 ~ 2000
找出数组中的所有 K 近邻下标

找出数组中的所有 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,这个数值是否有特别的含义或者是基于什么考虑?
在本题解中,选择在数组长度n的基础上加10主要是为了防止在进行差分数组操作时出现数组越界的情况。当元素的下标接近数组末尾时,右边界right可能会超出数组的实际长度。通过添加额外的空间(在这里是10个单位长度),可以确保即使在最极端的情况下(即k的值很大或数组末尾的元素是关键字),进行差分操作时也不会超出数组界限。这个数值10是一个保守的选择,足以处理大多数情况,但在某些特定情况下,根据k的具体大小和数组的长度,可能需要调整。
🦆
在处理边界条件时,您是如何确保不会出现数组越界的错误?具体是如何计算left和right边界的?
为了确保不会出现数组越界错误,我在计算影响区间的左边界(left)和右边界(right)时使用了Python的max和min函数。左边界left是通过`max(0, i - k)`计算的,这确保了即使i-k为负数(即i小于k),left的值也不会小于0,从而避免了负索引。右边界right是通过`min(n - 1, i + k)`计算的,这确保了即使i+k超出了数组的实际长度,right的值也不会超过数组的最大索引n-1。这样的处理方法可以有效防止数组越界。
🦆
差分数组diff中每个位置的值是如何表示当前元素是否受到key影响的?能否详细解释差分数组的工作原理及其如何通过累加来表示影响区间?
差分数组diff用于在数组中高效地表示区间增减。当我们想在原数组的某个区间[a, b]增加一个值时,可以在差分数组在a位置增加该值,在b+1位置减去该值。之后,通过对差分数组进行累加操作,可以得到每个位置的实际增加值。具体到本题,每当数组nums中的元素等于key时,会在diff的left位置加1(表示从这个位置开始受到影响),在right+1位置减1(表示在这个位置之后的第一个位置结束影响)。通过累加diff数组,每个位置的值如果不是0,则表示该位置在某个区间内受到了key的影响。这样,通过遍历累加后的diff数组,就可以得到所有受key影响的位置。
🦆
在最后收集结果的过程中,为什么可以直接遍历diff数组而不是nums数组来确定哪些下标是K近邻下标?
在最后收集结果的过程中,使用diff数组而非原始的nums数组进行遍历是因为diff数组在之前的操作中已经累加并反映了每个位置是否受到了key的影响。在累加后的diff数组中,任何非零的值都表示相应的位置在原数组中受到了key的影响。因此,直接遍历diff数组并收集那些值非零的索引即可得到所有K近邻下标。这种方法更为高效,因为它避免了重新检查nums中每个元素的状态,而是直接利用了之前计算的结果。

相关问题