1998. GCD Sort of an Array

题目信息

题号:

1998

难度:

Hard

主题:

并查集、数论、排序

原题:

LeetCode 1998

重点:

仅能交换最大公约数大于 1 的两个元素

题目重述

可以任意次交换数组中两个元素,条件是它们的最大公约数大于 1。判断能否把数组排成非递减顺序。

自建示例

输入:nums = [7,21,3]
输出:true
解释:先交换 7 与 21,再交换 21 与 3,可得到 [3,7,21]。
输入:nums = [5,2,3]
输出:false
解释:三个数两两互质,无法执行任何交换。