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 <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= space <= 10^9

解题思路

这道题的关键在于理解摧毁规律：如果选择 nums[i] 作为种子，那么所有满足 nums[i] + c * space 的目标都会被摧毁。

核心观察： 两个数 a 和 b 能被同一个种子摧毁，当且仅当它们对 space 的余数相同。因为如果 a % space == b % space，那么 a = k1 * space + r 和 b = k2 * space + r，选择较小的那个作为种子就能摧毁另一个。

解题思路：

  1. 使用哈希表统计每个余数值出现的次数，同时记录每个余数对应的最小值
  2. 找到出现次数最多的余数，如果有多个余数出现次数相同，选择对应最小值更小的那个
  3. 返回该余数对应的最小值

算法流程：

  • 遍历数组，对每个数计算 nums[i] % space
  • 用哈希表记录每个余数的出现次数和对应的最小原始值
  • 找到计数最大的余数，若计数相同则选最小值对应的余数
  • 返回结果

这种方法的时间复杂度为 O(n)，空间复杂度为 O(n)，是最优解法。

代码实现

class Solution {
public:
    int destroyTargets(vector<int>& nums, int space) {
        unordered_map<int, int> count;
        unordered_map<int, int> minVal;
        
        for (int num : nums) {
            int mod = num % space;
            count[mod]++;
            if (minVal.find(mod) == minVal.end() || num < minVal[mod]) {
                minVal[mod] = num;
            }
        }
        
        int maxCount = 0;
        int result = INT_MAX;
        
        for (auto& p : count) {
            int mod = p.first;
            int cnt = p.second;
            if (cnt > maxCount || (cnt == maxCount && minVal[mod] < result)) {
                maxCount = cnt;
                result = minVal[mod];
            }
        }
        
        return result;
    }
};

class Solution:
    def destroyTargets(self, nums: List[int], space: int) -> int:
        count = {}
        min_val = {}
        
        for num in nums:
            mod = num % space
            count[mod] = count.get(mod, 0) + 1
            if mod not in min_val or num < min_val[mod]:
                min_val[mod] = num
        
        max_count = 0
        result = float('inf')
        
        for mod, cnt in count.items():
            if cnt > max_count or (cnt == max_count and min_val[mod] < result):
                max_count = cnt
                result = min_val[mod]
        
        return result

public class Solution {
    public int DestroyTargets(int[] nums, int space) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        Dictionary<int, int> minVal = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            int mod = num % space;
            count[mod] = count.GetValueOrDefault(mod, 0) + 1;
            if (!minVal.ContainsKey(mod) || num < minVal[mod]) {
                minVal[mod] = num;
            }
        }
        
        int maxCount = 0;
        int result = int.MaxValue;
        
        foreach (var kvp in count) {
            int mod = kvp.Key;
            int cnt = kvp.Value;
            if (cnt > maxCount || (cnt == maxCount && minVal[mod] < result)) {
                maxCount = cnt;
                result = minVal[mod];
            }
        }
        
        return result;
    }
}

var destroyTargets = function(nums, space) {
    const remainderMap = new Map();
    
    for (const num of nums) {
        const remainder = num % space;
        if (!remainderMap.has(remainder)) {
            remainderMap.set(remainder, []);
        }
        remainderMap.get(remainder).push(num);
    }
    
    let maxCount = 0;
    let minSeed = Infinity;
    
    for (const [remainder, targets] of remainderMap) {
        if (targets.length > maxCount || (targets.length === maxCount && Math.min(...targets) < minSeed)) {
            maxCount = targets.length;
            minSeed = Math.min(...targets);
        }
    }
    
    return minSeed;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历数组一次，哈希表操作均为O(1)
空间复杂度O(n)最坏情况下所有数字的余数都不同，需要O(n)空间存储哈希表

相关题目