Easy

题目描述

给你两个整数数组 nums 和 divisors。

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

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

示例 1：

输入: nums = [2,9,15,50], divisors = [5,3,7,2]
输出: 2
解释:
divisors[0] 的可整除性分数是 2，因为 nums[2] 和 nums[3] 能被 5 整除。
divisors[1] 的可整除性分数是 2，因为 nums[1] 和 nums[2] 能被 3 整除。
divisors[2] 的可整除性分数是 0，因为 nums 中没有数能被 7 整除。
divisors[3] 的可整除性分数是 2，因为 nums[0] 和 nums[3] 能被 2 整除。
由于 divisors[0]、divisors[1] 和 divisors[3] 的分数相同，我们返回其中最小的 divisors[3]。

示例 2：

输入: nums = [4,7,9,3,9], divisors = [5,2,3]
输出: 3
解释:
divisors[0] 的可整除性分数是 0，因为 nums 中没有数能被 5 整除。
divisors[1] 的可整除性分数是 1，因为只有 nums[0] 能被 2 整除。
divisors[2] 的可整除性分数是 3，因为 nums[2]、nums[3] 和 nums[4] 能被 3 整除。

示例 3：

输入: nums = [20,14,21,10], divisors = [10,16,20]
输出: 10
解释:
divisors[0] 的可整除性分数是 2，因为 nums[0] 和 nums[3] 能被 10 整除。
divisors[1] 的可整除性分数是 0，因为 nums 中没有数能被 16 整除。
divisors[2] 的可整除性分数是 1，因为 nums[0] 能被 20 整除。

约束条件：

  • 1 <= nums.length, divisors.length <= 1000
  • 1 <= nums[i], divisors[i] <= 10^9

解题思路

这是一道相对简单的模拟题，我们需要计算每个除数的可整除性分数，然后找到最大分数对应的最小除数。

解题思路：

  1. 暴力计算：对于每个除数，遍历 nums 数组，统计能被该除数整除的数字个数。
  2. 跟踪最优解：在计算过程中同时跟踪最大分数和对应的最小除数。
  3. 处理并列情况：当遇到相同的最大分数时，选择较小的除数。

算法流程：

  • 初始化最大分数为 -1，结果为较大值
  • 遍历每个除数，计算其可整除性分数
  • 如果当前分数更大，或分数相等但除数更小，则更新结果
  • 返回最终结果

这种方法简单直接，时间复杂度虽然是 O(m×n)，但在给定的数据范围内完全可行。

推荐解法：暴力枚举，代码简洁且易于理解。

代码实现

class Solution {
public:
    int maxDivScore(vector<int>& nums, vector<int>& divisors) {
        int maxScore = -1;
        int result = INT_MAX;
        
        for (int divisor : divisors) {
            int score = 0;
            for (int num : nums) {
                if (num % divisor == 0) {
                    score++;
                }
            }
            
            if (score > maxScore || (score == maxScore && divisor < result)) {
                maxScore = score;
                result = divisor;
            }
        }
        
        return result;
    }
};

class Solution:
    def maxDivScore(self, nums: List[int], divisors: List[int]) -> int:
        max_score = -1
        result = float('inf')
        
        for divisor in divisors:
            score = sum(1 for num in nums if num % divisor == 0)
            
            if score > max_score or (score == max_score and divisor < result):
                max_score = score
                result = divisor
        
        return result

public class Solution {
    public int MaxDivScore(int[] nums, int[] divisors) {
        int maxScore = -1;
        int result = int.MaxValue;
        
        foreach (int divisor in divisors) {
            int score = 0;
            foreach (int num in nums) {
                if (num % divisor == 0) {
                    score++;
                }
            }
            
            if (score > maxScore || (score == maxScore && divisor < result)) {
                maxScore = score;
                result = divisor;
            }
        }
        
        return result;
    }
}

var maxDivScore = function(nums, divisors) {
    let maxScore = -1;
    let result = divisors[0];
    
    for (let divisor of divisors) {
        let score = 0;
        for (let num of nums) {
            if (num % divisor === 0) {
                score++;
            }
        }
        
        if (score > maxScore || (score === maxScore && divisor < result)) {
            maxScore = score;
            result = divisor;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(m × n)，其中 m 是 divisors 数组长度，n 是 nums 数组长度
空间复杂度O(1)，只使用了常数额外空间

相关题目