【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;}
};

Python

from typing import Listclass Solution:def maxDivScore(self, nums: List[int], divisors: List[int]) -> int:M, ans = -1, 0for d in divisors:thisCnt = 0for n in nums:thisCnt += n % d == 0if thisCnt > M:M = thisCntans = delif thisCnt == M:ans = min(ans, d)return ans

同步發文于CSDN和我的個人博客，原創不易，轉載經作者同意后請附上原文鏈接哦~

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