LeetCode 题解工作台
查询排序后的最大公约数
给你一个长度为 n 的整数数组 nums 和一个整数数组 queries 。 gcdPairs 表示数组 nums 中所有满足 0 的数对 (nums[i], nums[j]) 的 最大公约数 升序 排列构成的数组。 对于每个查询 queries[i] ，你需要找到 gcdPairs 中下标为 qu…
8
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们可以预处理得到数组 中的所有数对的最大公约数的出现次数，记录在数组 中。然后，我们计算数组 的前缀和。最后，对于每个查询，我们可以通过二分查找在数组 中找到第一个大于 的元素的下标，即为答案。 我们用 表示数组 中的最大值，用 记录数组 中每个数的出现次数。我们用 表示数组 中最大公约数等于 的数对个数。为了计算 ，我们可以按照以下步骤进行：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个长度为 n 的整数数组 nums 和一个整数数组 queries 。
gcdPairs 表示数组 nums 中所有满足 0 <= i < j < n 的数对 (nums[i], nums[j]) 的 最大公约数 升序 排列构成的数组。
对于每个查询 queries[i] ，你需要找到 gcdPairs 中下标为 queries[i] 的元素。
请你返回一个整数数组 answer ，其中 answer[i] 是 gcdPairs[queries[i]] 的值。
gcd(a, b) 表示 a 和 b 的 最大公约数 。
示例 1：
输入：nums = [2,3,4], queries = [0,2,2]
输出：[1,2,2]
解释：
gcdPairs = [gcd(nums[0], nums[1]), gcd(nums[0], nums[2]), gcd(nums[1], nums[2])] = [1, 2, 1].
升序排序后得到 gcdPairs = [1, 1, 2] 。
所以答案为 [gcdPairs[queries[0]], gcdPairs[queries[1]], gcdPairs[queries[2]]] = [1, 2, 2] 。
示例 2：
输入：nums = [4,4,2,1], queries = [5,3,1,0]
输出：[4,2,1,1]
解释：
gcdPairs 升序排序后得到 [1, 1, 1, 2, 2, 4] 。
示例 3：
输入：nums = [2,2], queries = [0,0]
输出：[2,2]
解释：
gcdPairs = [2] 。
提示：
2 <= n == nums.length <= 1051 <= nums[i] <= 5 * 1041 <= queries.length <= 1050 <= queries[i] < n * (n - 1) / 2
解题思路
方法一：预处理 + 前缀和 + 二分查找
我们可以预处理得到数组 中的所有数对的最大公约数的出现次数，记录在数组 中。然后，我们计算数组 的前缀和。最后，对于每个查询，我们可以通过二分查找在数组 中找到第一个大于 的元素的下标，即为答案。
我们用 表示数组 中的最大值，用 记录数组 中每个数的出现次数。我们用 表示数组 中最大公约数等于 的数对个数。为了计算 ，我们可以按照以下步骤进行：
- 计算数组 中 的倍数的出现次数 ，那么从这些元素中任选两个元素组成的数对一定满足最大公约数是 的倍数，即 需要增加 ；
- 我们需要排除最大公约数是 的倍数且大于 的数对，因此，对于 的倍数 ，我们需要减去 。
以上需要我们从大到小遍历 ，这样才能保证我们在计算 时已经计算了所有的 。
最后，我们计算数组 的前缀和，然后对于每个查询，我们可以通过二分查找在数组 中找到第一个大于 的元素的下标，即为答案。
时间复杂度 ，空间复杂度 。其中 和 分别是数组 的长度和最大值，而 是查询的数量。
class Solution:
def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:
mx = max(nums)
cnt = Counter(nums)
cnt_g = [0] * (mx + 1)
for i in range(mx, 0, -1):
v = 0
for j in range(i, mx + 1, i):
v += cnt[j]
cnt_g[i] -= cnt_g[j]
cnt_g[i] += v * (v - 1) // 2
s = list(accumulate(cnt_g))
return [bisect_right(s, q) for q in queries]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of distinct GCDs and the prefix sum processing, typically O(N log N + Q log M). Space complexity is O(M) for storing GCD counts and prefix sums. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate considers counting pairs instead of brute-force pair generation.
- question_mark
Mentions using hash maps to store GCD frequencies for fast queries.
- question_mark
Uses prefix sums or cumulative counts to answer multiple queries efficiently.
常见陷阱
外企场景- error
Attempting to generate all pairs explicitly, which leads to memory overflow on large arrays.
- error
Ignoring duplicates in nums, which affects the correct pair count for GCDs.
- error
Not using cumulative counts, resulting in O(N^2) query lookups.
进阶变体
外企场景- arrow_right_alt
Return the k-th largest GCD instead of the k-th smallest.
- arrow_right_alt
Handle dynamic updates to nums and answer queries in real time.
- arrow_right_alt
Count pairs with GCD divisible by a given integer instead of exact GCD values.