Leetcode 2453. Destroy Sequential Targets

[Woodyiiiiiii]

这道题我试了很久，但会一直TLE，无法找到门路。

卡在的点是：如何在数组内快速地(O(1)tp)找到某点及其延伸呢。

我做了两次尝试：

1. 循环数组，对每个数字都nums[i] + c * space循环，知道超过数组最大值，同时用hash剪纸，显然TLE，而且当数组数字内间隔大/space小的情况下，会更慢
2. 循环数组，再内部循环，两层循环+剪枝，尽量想把复杂度小于O(n^2)，但明显最坏的情况仍然是平方次。

以上都是很明显的错误做法，应该都不用写代码验证的！然后问题是如何快速找到数组内数字满足c * space的关系。

想一想，可以发现充分利用c * space这个条件，用数字%space对数字进行分组！然后再记录%完后同类数字的个数和最小值。

然后尽量使用Hash，不要用数组spaceCnt[space]来记录，因为space最大是10^9次方，会爆栈，同时会有很多空间没利用上，所以使用Map；而且用Map<Integer, List而不是Map<Integer, PriorityQueue<>>，免得再消耗时间。

class Solution {
    public int destroyTargets(int[] nums, int space) {
        int n = nums.length;
        int[] process = new int[n];
        Map<Integer, List<Integer>> spaceMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            process[i] = nums[i] % space;
            if (!spaceMap.containsKey(process[i])) {
                spaceMap.put(process[i], new ArrayList<>());
            }
            spaceMap.get(process[i]).add(nums[i]);
        }

        int maxCnt = 0;
        Set<Integer> maxSet = new HashSet<>();
        for (Map.Entry<Integer, List<Integer>> entry : spaceMap.entrySet()) {
            int cnt = entry.getValue().size();
            if (cnt > maxCnt) {
                maxCnt = cnt;
                maxSet.clear();
                maxSet.addAll(entry.getValue());
            } else if (cnt == maxCnt) {
                maxSet.addAll(entry.getValue());
            }
        }

        int min = Integer.MAX_VALUE, absMin = Integer.MAX_VALUE;
        for (int num : nums) {
            absMin = Math.min(absMin, num);
            if (maxSet.contains(num)) {
                min = Math.min(min, num);
            }
        }

        return min == Integer.MAX_VALUE ? absMin : min;
    }
}

可以观看做题记录中的两次错误TLE，还有两次AC，看到思路的进展！按道理这种题不用想这么久的！

---

• https://leetcode.com/problems/destroy-sequential-targets/description/