摧毁一系列目标
难度:
标签:
题目描述
代码结果
运行时间: 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的相对位置时使用了取模操作,这种方法是否能确保找到所有可能被摧毁的目标?
▷🦆
算法中使用了collections.Counter来统计各余数的频率,这种方法有没有可能错过某些可以摧毁更多目标的起始位置?
▷🦆
解题思路中提到,选出可以摧毁最多目标的起始位置中的最小值,这个最小值是怎样确定的?
▷