leetcode
leetcode 2101 ~ 2150
摧毁一系列目标

摧毁一系列目标

难度:

标签:

题目描述

代码结果

运行时间: 108 ms, 内存: 37.7 MB


/*
 * 思路:
 * 我们需要找到一个 nums[i],使得 nums[i] + c * space 能摧毁最多的目标。
 * 使用一个 HashMap 来记录每个 nums[i] 模 space 的出现次数。
 * 然后找到出现次数最多的那个值,并返回 nums[i] 中对应的最小值。
 * 使用 Java Stream 实现。
 */
import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public int destroyTargets(int[] nums, int space) {
        Map<Integer, Long> map = IntStream.of(nums).boxed()
            .collect(Collectors.groupingBy(num -> num % space, Collectors.counting()));
        long maxCount = map.values().stream().mapToLong(Long::longValue).max().orElse(0);
        return IntStream.of(nums)
            .filter(num -> map.get(num % space) == maxCount)
            .min().orElse(Integer.MAX_VALUE);
    }
}

解释

方法:

该题解的主要思路是首先对给定数组nums进行排序,以便在需要时能够快速地找到最小的起始点。接着,利用取模运算(num % space)计算每个数字与space的相对位置。这样,所有具有相同相对位置的数字将被同一次操作摧毁。这些计算结果存储在tmp_num列表中。之后,使用collections.Counter对tmp_num中的结果进行计数,统计每个余数出现的频率,这将帮助确定哪个起始位置可以摧毁最多的目标。最后,选出可以摧毁最多目标的起始位置中的最小值,通过查找该余数在tmp_num中的第一个索引并返回对应的nums中的值。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在解决这个问题时选择对数组进行排序?这对后续的计算有什么影响?
对数组进行排序主要是为了确保当我们找到可以摧毁最多目标的余数时,能够迅速地找到对应该余数的最小数值。排序后,同一余数的所有数值都将连续出现,因此可以通过简单地查找第一个出现该余数的位置来找到最小的数值。这样,我们不仅解决了问题,还确保了解的优化性(即最小化起始点)。
🦆
在计算每个数字与space的相对位置时使用了取模操作,这种方法是否能确保找到所有可能被摧毁的目标?
使用取模操作计算每个数字与space的相对位置是有效的,因为这反映了每个数字在被space整除时的余数。所有具有相同余数的数字可以通过一种操作同时被摧毁,因此这种方法确实能保证找到所有可能被一种操作摧毁的目标。
🦆
算法中使用了collections.Counter来统计各余数的频率,这种方法有没有可能错过某些可以摧毁更多目标的起始位置?
使用collections.Counter统计各余数的频率是准确的,因为它会考虑到所有出现的余数及其出现次数。该方法统计了每种余数出现的总次数,并没有错过任何数据。因此,它不会错过任何可以摧毁更多目标的起始位置。
🦆
解题思路中提到,选出可以摧毁最多目标的起始位置中的最小值,这个最小值是怎样确定的?
在已排序的数组中,最小值是通过首先找到可以摧毁最多目标的余数,然后在数组中找到此余数第一次出现的位置来确定的。由于数组已经是排序状态,所以该位置对应的值自然是该余数可对应的最小数值,从而保证了起始位置的最小性。

相关问题