2453-摧毁一系列目标

给你一个下标从 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

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场双周赛的看法~

---

根据题意，模 space 相同的数是可以被这些数中最小的那个数摧毁的。例如 space}=10，那么 3,13,23,33,\cdots 都可以被 3 摧毁。

因此按模 space 的结果分组，最大组的最小值就是答案。

[sol1-Python3]

class Solution:
    def destroyTargets(self, nums: List[int], space: int) -> int:
        g = defaultdict(list)
        for x in nums:
            g[x % space].append(x)
        mx = ans = 0
        for a in g.values():
            m, low = len(a), min(a)
            if m > mx or m == mx and low < ans:
                mx, ans = m, low
        return ans

[sol1-Go]

func destroyTargets(nums []int, space int) (ans int) {
	g := map[int][]int{}
	for _, x := range nums {
		g[x%space] = append(g[x%space], x)
	}
	mx := 0
	for _, a := range g {
		m := len(a)
		low := a[0]
		for _, x := range a {
			if x < low {
				low = x
			}
		}
		if m > mx || m == mx && low < ans {
			ans = low
			mx = m
		}
	}
	return
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为 nums 的长度。
• 空间复杂度：O(n)。