🔗 🟢 2644. Find the Maximum Divisibility Score 1258

tags: `Weekly Contest 341` `暴力法(Brute Force)`

題意

給定兩個下標從 $0$ 開始的整數陣列 $nums$ 和 $divisors$ ，對於每個 $divisors[i]$ ，計算 $nums$ 中可以被 $divisors[i]$ 整除的數字的數量。

返回能整除最多數字的 $divisors[i]$ ，如果有多個 $divisors[i]$ 具有譨整除相同數量的數字，則返回其中值最小的。

限制：

$1 \leq nums.length, divisors.length \leq 1000$
$1 \leq nums[i], divisors[i] \leq 10^9$

思路：暴力法(Brute Force)

從很小的數據範圍不難看出這題可以暴力解決，按照題意的方式枚舉 $divisors$ 中的每個數字，對於每個數字，計算 $nums$ 中可以被其整除的數字的數量，並更新答案即可。

存在一些透過排序優化的技巧，可以參考靈神的題解。

複雜度分析

時間複雜度： $O(n \times m)$ ，其中 $n$ 為 $nums$ 的長度， $m$ 為 $divisors$ 的長度。
空間複雜度： $O(1)$

class Solution:
    def maxDivScore(self, nums: List[int], divisors: List[int]) -> int:
        mx, ans = -1, 0
        for d in divisors:
            cur = 0 # count of numbers divisible by d
            for x in nums:
                if x % d == 0:
                    cur += 1
            if cur > mx or (cur == mx and d < ans): # update answer
                mx, ans = cur, d
        return ans

class Solution {
public:
    int maxDivScore(vector<int>& nums, vector<int>& divisors) {
        int mx = -1, ans = 0;
        for (int d : divisors) {
            int cur = 0;
            for (int x : nums) if (x % d ==0) cur++;
            if (cur > mx || cur == mx && d < ans) {
                mx = cur;
                ans = d;
            }
        }
        return ans;
    }
};