Loading... > https://leetcode.cn/problems/find-the-maximum-divisibility-score/description/?envType=daily-question&envId=2024-05-02 ### 暴力 简单题，暴力搜索即可。 ```c++ class Solution { public: int maxDivScore(std::vector<int>& nums, std::vector<int>& divisors) { std::sort(divisors.begin(), divisors.end()); int res = divisors[0], tmp, maximum = 0; for (auto &divisor : divisors) { tmp = 0; for (auto &num : nums) { if (num % divisor == 0) tmp += 1; } if (tmp > maximum) res = divisor, maximum = tmp; } return res; } }; ``` - 时间复杂度：$O(m \times n)$ ，其中 $n$ 为 `nums` 数组的长度， $m$ 为 `divisors` 数组的长度。 - 空间复杂度：$O(1)$ ，若考虑排序中的栈开销则为 $O(logm)$ 。 ### 优化 观察到 `nums` 中元素小于 `divisors` 的时候一定不能被整除，因此遇到这种情况直接终止内部的 `for` 循环即可。 ```c++ class Solution { public: int maxDivScore(std::vector<int>& nums, std::vector<int>& divisors) { std::sort(divisors.begin(), divisors.end()); std::sort(nums.begin(), nums.end(), std::greater<int>()); int res = divisors[0], count, maximum = 0; for (auto &divisor : divisors) { count = 0; for (auto &num : nums) { if (num < divisor) break; if (num % divisor == 0) count += 1; } if (count > maximum) res = divisor, maximum = count; } return res; } }; ``` - 时间复杂度：$O(nlogn + mn)$ ，其中 $n$ 为 `nums` 数组的长度， $m$ 为 `divisors` 数组的长度。 - 空间复杂度：$O(1)$ ，若考虑排序中的栈开销则为 $O(logm)$ 。 将 `divisors` 从小到大排序，并统计 `nums` 数组中的重复元素个数，记为 `dup` 。如果满足以下等式： $$ (maxinum - dup + 1) \cdot divisor > max(nums) $$ 则表示后面的 `divisor` 的可整除性得分不可能大于目前的最大值了。 假设 `divisor` 的可整除性得分大于目前的最大值，则一定有至少 `maxinum + 1` 个能被 `divisor` 整除的数。已知 `nums` 数组中有 `dup` 个重复的数，所以一定有 `maxinum - dup + 1` 个不同的 `divisor` 的倍数。而由 $(maxinum - dup + 1) \cdot divisor > max(nums)$ 可以得知 `nums` 中无法满足 `maxinum - dup + 1` 个不同的倍数，因此 `divisor` 的可整除性的风不可能大于目前的最大值。 由于 `divisors` 从小到大排序，所以遇到第一个满足条件的 `divisor` 就可以直接 `break` 外层的 `for` 循环了。 ```c++ class Solution { public: int maxDivScore(std::vector<int>& nums, std::vector<int>& divisors) { const int n = nums.size(); std::sort(divisors.begin(), divisors.end()); std::sort(nums.begin(), nums.end(), std::greater<int>()); int duplicate = 0; for (int i = 1; i < n; ++i) duplicate += nums[i] == nums[i - 1]; int res = divisors[0], count, maximum = 0; for (auto &divisor : divisors) { if (maximum - duplicate >= nums[0] / divisor) break; count = 0; for (auto &num : nums) { if (num < divisor) break; if (num % divisor == 0) ++count; } if (count > maximum) res = divisor, maximum = count; } return res; } }; ``` - 时间复杂度：$O(nlogn + mlogm + mn)$ ，其中 $n$ 为 `nums` 数组的长度， $m$ 为 `divisors` 数组的长度。 - 空间复杂度：$O(1)$ ，若考虑排序中的栈开销则为 $O(logm)$ 。 最后修改：2024 年 05 月 18 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏