找出可整除性得分最大的整数

难度: Easy

给你两个下标从 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] <= 10⁹

Submission

运行时间: 1574 ms

内存: 16.1 MB

class Solution:
    def maxDivScore(self, nums: List[int], divisors: List[int]) -> int:
        divisors.sort()
        maxScore, r = 0, divisors[0]
        nums.sort(reverse=True)
        for d in divisors:
            score = 0
            for n in nums:
                if n < d:
                    break
                if n % d == 0:
                    score += 1
            if score > maxScore:
                maxScore = score
                r = d
        return r

Explain

该题解采用了排序和暴力搜索的方法。首先对divisors数组进行升序排序，以便在遇到多个得分最大的整数时返回最小的一个。然后，对nums数组进行降序排序，这样在遍历nums时，一旦遇到小于当前divisor的元素，就可以提前终止内层循环，从而减少不必要的计算。接着，遍历每个divisor，计算其可整除性得分，并更新最大得分及对应的divisor。

时间复杂度: O(m log m + n log n + mn)

空间复杂度: O(1)

class Solution:
    def maxDivScore(self, nums: List[int], divisors: List[int]) -> int:
        divisors.sort()  # 对divisors进行升序排序
        maxScore, r = 0, divisors[0]  # 初始化最大得分和对应的divisor
        nums.sort(reverse=True)  # 对nums进行降序排序
        for d in divisors:  # 遍历每个divisor
            score = 0  # 初始化当前divisor的得分
            for n in nums:  # 遍历每个num
                if n < d:  # 如果num小于divisor，提前终止循环
                    break
                if n % d == 0:  # 如果num能被divisor整除，增加得分
                    score += 1
            if score > maxScore:  # 如果当前divisor的得分更高，更新最大得分和对应的divisor
                maxScore = score
                r = d
        return r  # 返回得分最高的divisor

Explore

对nums数组进行降序排序的目的是在内层循环中尽早发现不符合条件的情况从而提前终止循环，节省计算资源。在降序排序后，nums数组中的元素从大到小排列。当遍历这些元素时，一旦发现一个元素n小于当前的divisor，由于所有后续的元素都会更小（因为数组已经排序），它们也必然小于divisor，因此不可能被divisor整除。这时可以立即终止内层循环，避免了对后续更小的无效数字的无效检查。

如果在某一点上，divisor的得分已经等于nums数组的长度，这意味着所有nums中的元素都能被这个divisor整除。这已经是可能的最大得分，因此没有继续计算其他divisors得分的必要。这是因为得分不可能超过nums数组的长度，继续计算只会消耗额外的计算资源而不会改变结果。然而，如果得分没有达到这个最大可能值，那么仍需要继续遍历其他divisors，因为可能有更高得分的divisor存在。

主要作用是确保在找到多个具有相同最高得分的divisors时能返回最小的那个。升序排序确保了在更新得分记录时，较小的divisor会首先被考虑，从而在得分相同时自然选择最小的divisor。此外，从理论上讲，排序本身没有直接影响算法性能，因为不论如何排序，算法都需要遍历所有divisors来计算得分。因此，选择升序排序主要是为了满足题目要求返回最小的divisor。