数组的最大公因数排序

难度: Hard

给你一个整数数组 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 * 10⁴
2 <= nums[i] <= 10⁵

Submission

运行时间: 494 ms

内存: 55.5 MB

class Solution:
    def gcdSort(self, nums: List[int]) -> bool:

        def find(index: int) -> int:
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        
        def union(index1: int, index2: int):
            parent[find(index1)] = find(index2)

        st = set(nums)
        mx = max(nums)+1
        isp = [True]*(mx)
        parent = list(range(mx))
        for p in range(2,mx):
            if isp[p]:
                q = 2*p
                while q<mx:
                    isp[q]=False
                    if q in st:
                        union(q,p)
                    q+=p

        srt = sorted(nums)
        return all(nums[j]==srt[j] or find(nums[j])==find(srt[j]) for j in range(len(nums)))

Explain

本题解通过构建一个联合查找数据结构来解决问题。主要步骤包括初始化联合查找数组，筛选出所有的素数并将数组中的数与其最小的素因子进行连接。首先，定义每个数自身为其父节点。接着，通过埃拉托斯特尼筛法找出所有小于最大数+1的素数，并对于每个素数，遍历其倍数，如果倍数在数组中，将这个倍数与其最小素因子连接起来，形成一个联合查找组。最后，将原数组排序并比较原数组的每个元素与排序后数组的每个元素是否属于同一个联合查找组。如果所有元素都属于同一个组，说明可以通过交换使数组有序。

时间复杂度: O(m log m + n log log n)

空间复杂度: O(n + m)

class Solution:
    def gcdSort(self, nums: List[int]) -> bool:
        def find(index: int) -> int:
            if parent[index] != index:
                parent[index] = find(parent[index])  # 路径压缩
            return parent[index]
        
        def union(index1: int, index2: int):
            parent[find(index1)] = find(index2)  # 合并两个集合

        st = set(nums)
        mx = max(nums)+1
        isp = [True]*(mx)  # 素数筛
        parent = list(range(mx))  # 初始化联合查找数组
        for p in range(2,mx):
            if isp[p]:
                for q in range(p*2, mx, p):
                    isp[q]=False
                    if q in st:
                        union(q,p)  # 将倍数和素数连接
        
        srt = sorted(nums)  # 对数组排序
        return all(nums[j]==srt[j] or find(nums[j])==find(srt[j]) for j in range(len(nums)))  # 检查排序后是否所有元素都在同一集合

Explore

联合查找数据结构（也称为并查集）非常适合处理元素分组和组成员关系查询的问题，尤其是在需要频繁合并集合和查询集合归属的场景中。在这个问题中，需要判断数组是否可以通过交换变为有序状态，这涉及到判断数组中任意两个元素是否可以通过一系列交换到达彼此的位置。联合查找数据结构可以动态地合并任意两个元素的集合，并快速查询两个元素是否属于同一个集合，从而有效地解决问题。

埃拉托斯特尼筛法在这里用于生成小于等于数组中最大数`max(nums)`的所有素数。随后，对于每个筛选出的素数，通过遍历其倍数来检查这些倍数是否在数组`nums`中存在。如果存在，则这个倍数显然可以被当前素数整除，因此确认了该素数是此倍数的一个有效因子。这样，可以确保所有在数组中的数与其素数因子之间的关系被正确建立，从而在并查集中正确地连接它们。

在实现`union`函数之前，算法首先通过筛法找到所有可能的素数，然后遍历这些素数的倍数。在遍历倍数时，检查每个倍数是否在输入数组`nums`中。这是通过将数组元素存储在一个集合`st`中并使用`if q in st`来检查实现的。只有当倍数`q`确实在数组`nums`中时，`union`函数才会被调用来连接这个数`q`和它的素因子`p`。这样确保了`union`操作只在数组中实际存在的数及其素因子之间进行，从而维护了并查集的准确性和效率。