找出可整除性得分最大的整数
难度:
标签:
题目描述
You are given two 0-indexed integer arrays nums and divisors.
The divisibility score of divisors[i] is the number of indices j such that nums[j] is divisible by divisors[i].
Return the integer divisors[i] with the maximum divisibility score. If there is more than one integer with the maximum score, return the minimum of them.
Example 1:
Input: nums = [4,7,9,3,9], divisors = [5,2,3] Output: 3 Explanation: The divisibility score for every element in divisors is: The divisibility score of divisors[0] is 0 since no number in nums is divisible by 5. The divisibility score of divisors[1] is 1 since nums[0] is divisible by 2. The divisibility score of divisors[2] is 3 since nums[2], nums[3], and nums[4] are divisible by 3. Since divisors[2] has the maximum divisibility score, we return it.
Example 2:
Input: nums = [20,14,21,10], divisors = [5,7,5] Output: 5 Explanation: The divisibility score for every element in divisors is: The divisibility score of divisors[0] is 2 since nums[0] and nums[3] are divisible by 5. The divisibility score of divisors[1] is 2 since nums[1] and nums[2] are divisible by 7. The divisibility score of divisors[2] is 2 since nums[0] and nums[3] are divisible by 5. Since divisors[0], divisors[1], and divisors[2] all have the maximum divisibility score, we return the minimum of them (i.e., divisors[2]).
Example 3:
Input: nums = [12], divisors = [10,16] Output: 10 Explanation: The divisibility score for every element in divisors is: The divisibility score of divisors[0] is 0 since no number in nums is divisible by 10. The divisibility score of divisors[1] is 0 since no number in nums is divisible by 16. Since divisors[0] and divisors[1] both have the maximum divisibility score, we return the minimum of them (i.e., divisors[0]).
Constraints:
1 <= nums.length, divisors.length <= 10001 <= nums[i], divisors[i] <= 109
代码结果
运行时间: 1574 ms, 内存: 16.1 MB
/*
思路：
1. 使用 Java Stream API 来计算每个除数的可整除性得分。
2. 创建一个 Map 来存储每个除数及其对应的得分。
3. 使用 Stream 的 max 方法找到得分最大且数值最小的除数。
4. 返回该除数。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int maxDivScore(int[] nums, int[] divisors) {
Map<Integer, Long> scores = Arrays.stream(divisors)
.boxed()
.collect(Collectors.toMap(d -> d, d -> Arrays.stream(nums).filter(n -> n % d == 0).count()));
return scores.entrySet().stream()
.max(Comparator.comparing((Map.Entry<Integer, Long> entry) -> entry.getValue())
.thenComparing(Map.Entry::getKey, Comparator.reverseOrder()))
.get()
.getKey();
}
}解释
方法:
该题解采用了排序和暴力搜索的方法。首先对divisors数组进行升序排序，以便在遇到多个得分最大的整数时返回最小的一个。然后，对nums数组进行降序排序，这样在遍历nums时，一旦遇到小于当前divisor的元素，就可以提前终止内层循环，从而减少不必要的计算。接着，遍历每个divisor，计算其可整除性得分，并更新最大得分及对应的divisor。
时间复杂度:
O(m log m + n log n + mn)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在计算可整除性得分时要先对nums数组进行降序排序？这种排序方式如何帮助提前终止内层循环？
▷🦆
在遍历divisors数组时，如果当前divisor的得分已经超过了某个阈值（例如所有nums元素的数量），是否有必要继续计算后续divisors的得分？
▷🦆
对于divisors的排序，为什么选择升序排序？升序排序除了在得分相同时返回最小的divisor外，还有其他作用吗？
▷