【LetMeFly】2644.找出可整除性得分最大的整數(shù)：暴力模擬（兩層循環(huán)）

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

給你兩個(gè)下標(biāo)從 0 開(kāi)始的整數(shù)數(shù)組 nums 和 divisors 。

divisors[i] 的 可整除性得分 等于滿足 nums[j] 能被 divisors[i] 整除的下標(biāo) j 的數(shù)量。

返回 可整除性得分 最大的整數(shù) divisors[i] 。如果有多個(gè)整數(shù)具有最大得分，則返回?cái)?shù)值最小的一個(gè)。

?

示例 1：

輸入：nums = [4,7,9,3,9], divisors = [5,2,3]
輸出：3
解釋：divisors 中每個(gè)元素的可整除性得分為：
divisors[0] 的可整除性得分為 0 ，因?yàn)?nums 中沒(méi)有任何數(shù)字能被 5 整除。
divisors[1] 的可整除性得分為 1 ，因?yàn)?nums[0] 能被 2 整除。 
divisors[2] 的可整除性得分為 3 ，因?yàn)?nums[2]、nums[3] 和 nums[4] 都能被 3 整除。 
因此，返回 divisors[2] ，它的可整除性得分最大。

示例 2：

輸入：nums = [20,14,21,10], divisors = [5,7,5]
輸出：5
解釋：divisors 中每個(gè)元素的可整除性得分為：
divisors[0] 的可整除性得分為 2 ，因?yàn)?nums[0] 和 nums[3] 都能被 5 整除。
divisors[1] 的可整除性得分為 2 ，因?yàn)?nums[1] 和 nums[2] 都能被 7 整除。
divisors[2] 的可整除性得分為 2 ，因?yàn)?nums[0] 和 nums[3] 都能被5整除。 
由于 divisors[0]、divisors[1] 和 divisors[2] 的可整除性得分都是最大的，因此，我們返回?cái)?shù)值最小的一個(gè)，即 divisors[2] 。

示例 3：

輸入：nums = [12], divisors = [10,16]
輸出：10
解釋：divisors 中每個(gè)元素的可整除性得分為：
divisors[0] 的可整除性得分為 0 ，因?yàn)?nums 中沒(méi)有任何數(shù)字能被 10 整除。
divisors[1] 的可整除性得分為 0 ，因?yàn)?nums 中沒(méi)有任何數(shù)字能被 16 整除。 
由于 divisors[0] 和 divisors[1] 的可整除性得分都是最大的，因此，我們返回?cái)?shù)值最小的一個(gè)，即 divisors[0] 。

?

提示：

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

解題方法：兩層循環(huán)枚舉

外層循環(huán)遍歷每一個(gè)“被除數(shù)”，對(duì)于某個(gè)被除數(shù)$d$，記錄其“可整除性得分”。

• 如果這個(gè)得分大于歷史最大得分，更新最大得分并將其暫時(shí)視為答案；
• 如果這個(gè)得分等于歷史最大得分，將它和“臨時(shí)答案”中最小的那個(gè)暫時(shí)視為答案。

最終的“臨時(shí)答案”即為最終答案。

• 時(shí)間復(fù)雜度$O(len(nums)\times len(divisors))$
• 空間復(fù)雜度$O(N\log N)$

本題似乎沒(méi)有更小的時(shí)空復(fù)雜度的算法，能做的似乎最多是一些剪枝。

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

同步發(fā)文于CSDN和我的個(gè)人博客，原創(chuàng)不易，轉(zhuǎn)載經(jīng)作者同意后請(qǐng)附上原文鏈接哦~

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