本文涉及知识点

数论：质数、最大公约数、菲蜀定理

LeetCode2453. 摧毁一系列目标

给你一个下标从 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⁵
1 <= nums[i] <= 10⁹
1 <= space <= 10⁹

同余

%space相同的数，选择最小的数，可以一起摧毁。本题$⟺$ ，求同余最多的数。
最简洁的写法：降序排序后，cnt[n%space] if( cnt[n%space] >= canCnt) ans = n canCnt = cnt[n%space]

代码

核心代码

class Solution {
		public:
			int destroyTargets(vector<int>& nums, int space) {
				sort(nums.begin(), nums.end(), greater<>());
				unordered_map<int,int> cnt;
				int canCnt = 0;
				int ans = INT_MAX;
				for (const auto n : nums) {
					const auto t = n % space;
					cnt[t]++;
					if (cnt[t] >= canCnt) {
						canCnt = cnt[t];
						ans = n;
					}
				}
				return ans;
			}
		};

单元测试

	vector<int> nums;
		int space;
		TEST_METHOD(TestMethod11)
		{
			nums = { 3, 7, 8, 1, 1, 5 }, space = 2;
			auto res = Solution().destroyTargets(nums, space);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1,3,5,2,4,6 }, space = 2;
			auto res = Solution().destroyTargets(nums, space);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 6,2,5 }, space = 100;
			auto res = Solution().destroyTargets(nums, space);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod14)
		{
			nums = { 691 }, space = 4;
			auto res = Solution().destroyTargets(nums, space);
			AssertEx(691, res);
		}
		TEST_METHOD(TestMethod15)
		{
			nums = { 1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000 }, space = 1000000000;
			auto res = Solution().destroyTargets(nums, space);
			AssertEx(1, res);
		}