数组的最大公因数排序

/*
 * Solution approach using Java Streams:
 * 1. Create a sorted copy of the array, sortedNums.
 * 2. Identify the components of connected elements using Union-Find by calculating gcd for each pair.
 * 3. Use Stream operations to handle arrays and collections.
 */

import java.util.*;
import java.util.stream.*;

public class SolutionStream {
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public boolean canSortByGCD(int[] nums) {
        int[] sortedNums = Arrays.stream(nums).sorted().toArray();
        UnionFind uf = new UnionFind(100001);

        IntStream.range(0, nums.length).forEach(i ->
            IntStream.range(i + 1, nums.length).forEach(j -> {
                if (gcd(nums[i], nums[j]) > 1) {
                    uf.union(nums[i], nums[j]);
                }
            })
        );

        return IntStream.range(0, nums.length).allMatch(i ->
            uf.find(nums[i]) == uf.find(sortedNums[i])
        );
    }

    class UnionFind {
        private int[] parent;

        public UnionFind(int size) {
            parent = new int[size];
            Arrays.setAll(parent, i -> i);
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                parent[rootY] = rootX;
            }
        }
    }
}