跳转至

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

题目描述

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

divisors[i] 的 可整除性得分 等于满足 nums[j] 能被 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] 、divisor[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 整除。

因为 divisors[0] 的可整除性分数最大，我们返回 divisors[0]。

 

提示：

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

解法

方法一：枚举

我们可以枚举 \(divisors\) 中的每个元素 \(div\)，计算 \(nums\) 中有多少个元素能被 \(div\) 整除，记为 \(cnt\)。

  • 如果 \(cnt\) 大于当前最大的可整除性得分 \(mx\)，则更新 \(mx = cnt\)，并且更新 \(ans = div\)。
  • 如果 \(cnt\) 等于 \(mx\) 并且 \(div\) 小于 \(ans\)，则更新 \(ans = div\)。

最后返回 \(ans\) 即可。

时间复杂度 \((m \times n)\)，其中 \(m\) 和 \(n\) 分别是 \(nums\) 和 \(divisors\) 的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maxDivScore(self, nums: List[int], divisors: List[int]) -> int:
        ans, mx = divisors[0], 0
        for div in divisors:
            cnt = sum(x % div == 0 for x in nums)
            if mx < cnt:
                mx, ans = cnt, div
            elif mx == cnt and ans > div:
                ans = div
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxDivScore(int[] nums, int[] divisors) {
        int ans = divisors[0];
        int mx = 0;
        for (int div : divisors) {
            int cnt = 0;
            for (int x : nums) {
                if (x % div == 0) {
                    ++cnt;
                }
            }
            if (mx < cnt) {
                mx = cnt;
                ans = div;
            } else if (mx == cnt) {
                ans = Math.min(ans, div);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxDivScore(vector<int>& nums, vector<int>& divisors) {
        int ans = divisors[0];
        int mx = 0;
        for (int div : divisors) {
            int cnt = 0;
            for (int x : nums) {
                cnt += x % div == 0;
            }
            if (mx < cnt) {
                mx = cnt;
                ans = div;
            } else if (mx == cnt) {
                ans = min(ans, div);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func maxDivScore(nums []int, divisors []int) int {
    ans, mx := divisors[0], 0
    for _, div := range divisors {
        cnt := 0
        for _, x := range nums {
            if x%div == 0 {
                cnt++
            }
        }
        if mx < cnt {
            ans, mx = div, cnt
        } else if mx == cnt && ans > div {
            ans = div
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function maxDivScore(nums: number[], divisors: number[]): number {
    let ans: number = divisors[0];
    let mx: number = 0;
    for (const div of divisors) {
        const cnt = nums.reduce((a, b) => a + (b % div == 0 ? 1 : 0), 0);
        if (mx < cnt) {
            mx = cnt;
            ans = div;
        } else if (mx === cnt && ans > div) {
            ans = div;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
    pub fn max_div_score(nums: Vec<i32>, divisors: Vec<i32>) -> i32 {
        let mut ans = divisors[0];
        let mut mx = 0;

        for &div in &divisors {
            let mut cnt = 0;

            for &n in &nums {
                if n % div == 0 {
                    cnt += 1;
                }
            }

            if cnt > mx || (cnt >= mx && div < ans) {
                mx = cnt;
                ans = div;
            }
        }

        ans
    }
}

评论