前言
经过前期的基础训练以及部分实战练习，粗略掌握了各种题型的解题思路。现阶段开始专项练习。
数论包含最大公约数(>=2个数)、最大公约数性质、最小公倍数、区间范围质因素计数(最下间隔)、质因素分解、判断质数、平方根、立方根、互质、同余等等。
描述
给你一个下标从 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 <= 1051 <= nums[i] <= 1091 <= space <= 109
实现原理与步骤
1.nums[i] + c * space转换意思为两数相差c*space.模 space 相同的数是可以被这些数中最小的那个数摧毁的.
2.按模space相同数最大分组的最小值。
实现代码(按模分组)
import java.util.*;
class Solution {
public int destroyTargets(int[] nums, int space) {
// 使用HashMap存储按模space分组的数字
Map<Integer, List<Integer>> g = new HashMap<>();
// 按模space值将每个数字进行分组
for (int x : nums) {
int key = x % space;
if (!g.containsKey(key)) {
g.put(key, new ArrayList<>());
}
g.get(key).add(x);
}
// 初始化变量以追踪最大组大小和最大组中最小的值
int mx = 0;
int ans = Integer.MAX_VALUE;
// 遍历每个组
for (List<Integer> a : g.values()) {
int m = a.size();
int low = Collections.min(a);
// 如果当前组大小大于最大组大小，或者当前组大小等于最大组大小但最小值更小，则更新最大组大小和最小值
if (m > mx || (m == mx && low < ans)) {
mx = m;
ans = low;
}
}
// 返回最大组中的最小值
return ans;
}
}
实现代码(枚举超时)
class Solution {
public int destroyTargets(int[] nums, int space) {
int res = Integer.MAX_VALUE;
int maxCount = 0;
for (int i = 0; i < nums.length; i++) {
int temp = 0;
for (int j = 0; j < nums.length; j++) {
if (i != j) {
if (Math.abs(nums[j] - nums[i]) % space == 0) {
temp++;
}
}
}
if (temp > maxCount) {
maxCount = temp;
res = nums[i];
} else if (temp == maxCount) {
res = Math.min(res, nums[i]);
}
}
return res;
}
}