侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【脑筋急转弯】摧毁一系列目标【力扣第 90 场双周赛】

GabrielxD
2022-10-30 / 0 评论 / 0 点赞 / 11 阅读 / 589 字 / 正在检测是否收录...

题目

6226. 摧毁一系列目标


给你一个下标从 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 的目标”,反过来说就是 nums[x] 会被 nums[x] % space 给摧毁,所以我们可以把 nums 中所有元素按照其与 space 的模分组,然后找到最大分组最小值即是答案。

代码

class Solution {
    public int destroyTargets(int[] nums, int space) {
        int max = 0, maxRemain = 0;
        Map<Integer, Integer> mp1 = new HashMap<>(), mp2 = new HashMap<>();
        for (int num : nums) {
            int remain = num % space;
            int cnt = mp1.getOrDefault(remain, 0) + 1;
            mp1.put(remain, cnt);
            int minNum = mp2.getOrDefault(remain, Integer.MAX_VALUE);
            if (num < minNum) {
                mp2.put(remain, num);
                minNum = num;
            }
            if (cnt > max || (cnt == max && minNum < mp2.getOrDefault(maxRemain, Integer.MAX_VALUE))) {
                max = cnt;
                maxRemain = remain;
            }
        }
        return mp2.get(maxRemain);
    }
}
0

评论区