class Solution {
public:
bool gcdSort(vector<int>& nums) {
}
};
1998. 数组的最大公因数排序
给你一个整数数组 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原站题解
java 解法, 执行用时: 229 ms, 内存消耗: 48.8 MB, 提交时间: 2023-09-17 11:55:27
class UnionFind
{
int [] parent;
int [] size;
UnionFind(int n)
{
parent = new int [n];
size = new int [n];
for (int x = 0; x < n; x ++)
parent[x] = x;
Arrays.fill(size, 1);
}
public int Find(int x)
{
if (parent[x] != x)
parent[x] = Find(parent[x]);
return parent[x];
}
public boolean Union(int x, int y)
{
int root_x = Find(x);
int root_y = Find(y);
if (root_x == root_y)
return false;
if (size[root_x] > size[root_y])
{
int tmp = root_x;
root_x = root_y;
root_y = tmp;
}
parent[root_x] = root_y;
size[root_y] += size[root_x];
return true;
}
public boolean connected(int x, int y)
{
return Find(x) == Find(y);
}
}
class Solution
{
public boolean gcdSort(int[] nums)
{
int N = 100010;
UnionFind UF = new UnionFind(N);
int n = nums.length;
for (int x : nums)
{
int a = 2;
while (a * a <= x)
{
if (x % a == 0)
{
int b = x / a;
UF.Union(x, a);
UF.Union(x, b);
}
a ++;
}
}
int [] tar = Arrays.copyOfRange(nums, 0, n);
Arrays.sort(tar);
for (int i = 0; i < n; i ++)
{
int x = nums[i];
int y = tar[i];
if (UF.connected(x, y) == false)
return false;
}
return true;
}
}
python3 解法, 执行用时: 7640 ms, 内存消耗: 23.6 MB, 提交时间: 2023-09-17 11:54:52
class UnionFind:
def __init__(self, n: int):
self.parent = [x for x in range(n)]
self.size = [1 for x in range(n)]
def Find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.Find(self.parent[x])
return self.parent[x]
def Union(self, x: int, y: int) -> bool:
root_x = self.Find(x)
root_y = self.Find(y)
if root_x == root_y:
return False
if self.size[root_x] > self.size[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_x] = root_y
self.size[root_y] += self.size[root_x]
return True
def connected(self, x: int, y: int) -> bool:
return self.Find(x) == self.Find(y)
class Solution:
def gcdSort(self, nums: List[int]) -> bool:
N = 10 ** 5 + 1
UF = UnionFind(N)
n = len(nums)
for x in nums:
a = 2
while a * a <= x:
if x % a == 0:
b = x // a
UF.Union(x, a)
UF.Union(x, b)
a += 1
tar = sorted(nums)
for i in range(n):
x = nums[i]
y = tar[i]
if UF.connected(x, y) == False:
return False
return True
cpp 解法, 执行用时: 192 ms, 内存消耗: 52.1 MB, 提交时间: 2023-09-17 11:54:16
const int N = 3e5 + 10;
class Solution {
private:
int p[N];
public:
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
void merge(int a, int b) {
int x = find(a), y = find(b);
if (x == y) return;
p[x] = y;
}
bool gcdSort(vector<int>& nums) {
vector<int> nums1 = nums;
for (int i = 1; i < N; i++) p[i] = i;
// 分解质因数
for (auto c:nums) {
int k = c;
for (int i = 2; i <= c / i; i++) {
bool flag = false;
while (c % i == 0)
c /= i, flag = true;
if (flag)
merge(k, i);
}
// 合并质因子
if (c > 1)
merge(k, c);
}
sort(nums1.begin(), nums1.end());
// 对比原数组
for (int i = 0; i < nums1.size(); i++) {
if (nums1[i] == nums[i]) continue;
if (find(nums1[i]) != find(nums[i])) return false;
}
return true;
}
};
golang 解法, 执行用时: 508 ms, 内存消耗: 39.5 MB, 提交时间: 2023-09-17 11:53:58
const mx int = 1e5
var pf [mx + 1][]int
func init() { // 预处理每个数的质因子
for i := 2; i <= mx; i++ {
if pf[i] == nil {
for j := i; j <= mx; j += i {
pf[j] = append(pf[j], i)
}
}
}
}
func gcdSort(a []int) bool {
n := len(a)
u := newUnionFind(n + mx)
for i, v := range a {
for _, p := range pf[v] {
u.merge(i, p+n) // 用并查集将下标 i 和质数 p 合并，为了区分下标集合和质数集合，将 p 加上 n
}
}
// 整理处于同一集合的元素及其下标
groups := make([]struct{ vs, is []int }, mx)
for i, v := range a {
p := u.find(i) - n
groups[p].vs = append(groups[p].vs, v)
groups[p].is = append(groups[p].is, i)
}
// 每一组内的元素可以直接或间接交换，因此对每组元素直接排序，然后按照在原数组中的顺序填回去
for _, g := range groups {
sort.Ints(g.vs)
for j, v := range g.vs {
a[g.is[j]] = v
}
}
return sort.IntsAreSorted(a) // 判断数组是否有序
}
type uf struct {
fa []int
}
func newUnionFind(n int) uf {
fa := make([]int, n)
for i := range fa {
fa[i] = i
}
return uf{fa}
}
func (u uf) find(x int) int {
if u.fa[x] != x {
u.fa[x] = u.find(u.fa[x])
}
return u.fa[x]
}
func (u uf) merge(from, to int) {
u.fa[u.find(from)] = u.find(to)
}