摧毁一系列目标

标签: 数组 哈希表 计数

难度: Medium

给你一个下标从 0 开始的数组 nums ，它包含若干正整数，表示数轴上你需要摧毁的目标所在的位置。同时给你一个整数 space 。

你有一台机器可以摧毁目标。给机器 输入 nums[i] ，这台机器会摧毁所有位置在 nums[i] + c * space 的目标，其中 c 是任意非负整数。你想摧毁 nums 中 尽可能多 的目标。

请你返回在摧毁数目最多的前提下，nums[i] 的 最小值 。

示例 1：

输入：nums = [3,7,8,1,1,5], space = 2
输出：1
解释：如果我们输入 nums[3] ，我们可以摧毁位于 1,3,5,7,9,... 这些位置的目标。
这种情况下， 我们总共可以摧毁 5 个目标（除了 nums[2]）。
没有办法摧毁多于 5 个目标，所以我们返回 nums[3] 。

示例 2：

输入：nums = [1,3,5,2,4,6], space = 2
输出：1
解释：输入 nums[0] 或者 nums[3] 都会摧毁 3 个目标。
没有办法摧毁多于 3 个目标。
由于 nums[0] 是最小的可以摧毁 3 个目标的整数，所以我们返回 1 。

示例 3：

输入：nums = [6,2,5], space = 100
输出：2
解释：无论我们输入哪个数字，都只能摧毁 1 个目标。输入的最小整数是 nums[1] 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= space <= 109

Submission

运行时间: 108 ms

内存: 37.7 MB

import collections
class Solution:
    def destroyTargets(self, nums: List[int], space: int) -> int:
        nums.sort()
        tmp_num = [num % space for num in nums]
        tmp = collections.Counter(tmp_num)
        ans = max(tmp, key=tmp.get)
        return nums[tmp_num.index(ans)]

Explain

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

时间复杂度: O(n log n)

空间复杂度: O(n)

import collections
class Solution:
    def destroyTargets(self, nums: List[int], space: int) -> int:
        nums.sort()  # 对nums进行排序
        tmp_num = [num % space for num in nums]  # 计算每个数相对于space的余数
        tmp = collections.Counter(tmp_num)  # 对余数进行计数
        ans = max(tmp, key=tmp.get)  # 找出能摧毁最多目标的余数
        return nums[tmp_num.index(ans)]  # 返回能摧毁最多目标的余数对应的最小nums值

Explore

对数组进行排序主要是为了确保当我们找到可以摧毁最多目标的余数时，能够迅速地找到对应该余数的最小数值。排序后，同一余数的所有数值都将连续出现，因此可以通过简单地查找第一个出现该余数的位置来找到最小的数值。这样，我们不仅解决了问题，还确保了解的优化性（即最小化起始点）。

使用取模操作计算每个数字与space的相对位置是有效的，因为这反映了每个数字在被space整除时的余数。所有具有相同余数的数字可以通过一种操作同时被摧毁，因此这种方法确实能保证找到所有可能被一种操作摧毁的目标。

使用collections.Counter统计各余数的频率是准确的，因为它会考虑到所有出现的余数及其出现次数。该方法统计了每种余数出现的总次数，并没有错过任何数据。因此，它不会错过任何可以摧毁更多目标的起始位置。

在已排序的数组中，最小值是通过首先找到可以摧毁最多目标的余数，然后在数组中找到此余数第一次出现的位置来确定的。由于数组已经是排序状态，所以该位置对应的值自然是该余数可对应的最小数值，从而保证了起始位置的最小性。