LeetCode 题解工作台
数组的最大公因数排序
给你一个整数数组 nums ，你可以在 nums 上执行下述操作 任意次 ： 如果 gcd(nums[i], nums[j]) > 1 ，交换 nums[i] 和 nums[j] 的位置。其中 gcd(nums[i], nums[j]) 是 nums[i] 和 nums[j] 的最大公因数。 如果能…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·数学
答案摘要
class Solution: def gcdSort(self, nums: List[int]) -> bool:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个整数数组 nums ，你可以在 nums 上执行下述操作 任意次 ：
- 如果
gcd(nums[i], nums[j]) > 1，交换nums[i]和nums[j]的位置。其中gcd(nums[i], nums[j])是nums[i]和nums[j]的最大公因数。
如果能使用上述交换方式将 nums 按 非递减顺序 排列，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [7,21,3] 输出：true 解释：可以执行下述操作完成对 [7,21,3] 的排序： - 交换 7 和 21 因为 gcd(7,21) = 7 。nums = [21,7,3] - 交换 21 和 3 因为 gcd(21,3) = 3 。nums = [3,7,21]
示例 2：
输入：nums = [5,2,6,2] 输出：false 解释：无法完成排序，因为 5 不能与其他元素交换。
示例 3：
输入：nums = [10,5,9,3,15] 输出：true 解释： 可以执行下述操作完成对 [10,5,9,3,15] 的排序： - 交换 10 和 15 因为 gcd(10,15) = 5 。nums = [15,5,9,3,10] - 交换 15 和 3 因为 gcd(15,3) = 3 。nums = [3,5,9,15,10] - 交换 10 和 15 因为 gcd(10,15) = 5 。nums = [3,5,9,10,15]
提示：
1 <= nums.length <= 3 * 1042 <= nums[i] <= 105
解题思路
方法一
class Solution:
def gcdSort(self, nums: List[int]) -> bool:
n = 10**5 + 10
p = list(range(n))
f = defaultdict(list)
mx = max(nums)
for i in range(2, mx + 1):
if f[i]:
continue
for j in range(i, mx + 1, i):
f[j].append(i)
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
for i in nums:
for j in f[i]:
p[find(i)] = find(j)
s = sorted(nums)
for i, num in enumerate(nums):
if s[i] != num and find(num) != find(s[i]):
return False
return True
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a clear understanding of graph theory and its application to number theory problems.
- question_mark
Evaluate the candidate's ability to optimize Union-Find operations for efficiency.
- question_mark
Assess how the candidate handles edge cases where gcd connections are sparse or absent.
常见陷阱
外企场景- error
Misunderstanding gcd relationships can lead to incorrect union operations.
- error
Failing to optimize the Union-Find structure for large inputs.
- error
Not correctly checking if sorting is achievable once components are identified.
进阶变体
外企场景- arrow_right_alt
Consider variations where only some elements can be swapped (restricted gcd conditions).
- arrow_right_alt
What happens if you are given a fixed number of allowed swaps?
- arrow_right_alt
How would the problem change if instead of gcd, you had to check for divisibility?