LeetCode 2644.找出可整除性得分最大的整数：暴力模拟（两层循环）

【LetMeFly】2644.找出可整除性得分最大的整数：暴力模拟（两层循环）

力扣题目链接：https://leetcode.cn/problems/find-the-maximum-divisibility-score/

给你两个下标从 0 开始的整数数组 nums 和 divisors 。

divisors[i] 的 可整除性得分 等于满足 nums[j] 能被 divisors[i] 整除的下标 j 的数量。

返回 可整除性得分 最大的整数 divisors[i] 。如果有多个整数具有最大得分，则返回数值最小的一个。

 

示例 1：

输入：nums = [4,7,9,3,9], divisors = [5,2,3]
输出：3
解释：divisors 中每个元素的可整除性得分为：
divisors[0] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 5 整除。
divisors[1] 的可整除性得分为 1 ，因为 nums[0] 能被 2 整除。 
divisors[2] 的可整除性得分为 3 ，因为 nums[2]、nums[3] 和 nums[4] 都能被 3 整除。 
因此，返回 divisors[2] ，它的可整除性得分最大。

示例 2：

输入：nums = [20,14,21,10], divisors = [5,7,5]
输出：5
解释：divisors 中每个元素的可整除性得分为：
divisors[0] 的可整除性得分为 2 ，因为 nums[0] 和 nums[3] 都能被 5 整除。
divisors[1] 的可整除性得分为 2 ，因为 nums[1] 和 nums[2] 都能被 7 整除。
divisors[2] 的可整除性得分为 2 ，因为 nums[0] 和 nums[3] 都能被5整除。 
由于 divisors[0]、divisors[1] 和 divisors[2] 的可整除性得分都是最大的，因此，我们返回数值最小的一个，即 divisors[2] 。

示例 3：

输入：nums = [12], divisors = [10,16]
输出：10
解释：divisors 中每个元素的可整除性得分为：
divisors[0] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 10 整除。
divisors[1] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 16 整除。 
由于 divisors[0] 和 divisors[1] 的可整除性得分都是最大的，因此，我们返回数值最小的一个，即 divisors[0] 。

 

提示：

• 1 <= nums.length, divisors.length <= 1000
• 1 <= nums[i], divisors[i] <= 109

解题方法：两层循环枚举

外层循环遍历每一个“被除数”，对于某个被除数$d$，记录其“可整除性得分”。

• 如果这个得分大于历史最大得分，更新最大得分并将其暂时视为答案；
• 如果这个得分等于历史最大得分，将它和“临时答案”中最小的那个暂时视为答案。

最终的“临时答案”即为最终答案。

• 时间复杂度$O(len(nums)\times len(divisors))$
• 空间复杂度$O(N\log N)$

本题似乎没有更小的时空复杂度的算法，能做的似乎最多是一些剪枝。

AC代码

C++

class Solution {
public:
    int maxDivScore(vector<int>& nums, vector<int>& divisors) {
        int M = -1, ans = 0;
        for (int d : divisors) {
            int thisCnt = 0;
            for (int n : nums) {
                if (n % d == 0) {
                    thisCnt++;
                }
            }
            if (thisCnt > M) {
                M = thisCnt;
                ans = d;
            }
            else if (thisCnt == M) {
                M = thisCnt;
                ans = min(ans, d);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Python

from typing import List

class Solution:
    def maxDivScore(self, nums: List[int], divisors: List[int]) -> int:
        M, ans = -1, 0
        for d in divisors:
            thisCnt = 0
            for n in nums:
                thisCnt += n % d == 0
            if thisCnt > M:
                M = thisCnt
                ans = d
            elif thisCnt == M:
                ans = min(ans, d)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/139026732