https://leetcode.com/problems/gcd-sort-of-an-array/
方法还是很巧妙的，也很考验编程的基本功，记下来备忘。

个人题解

  1. func gcdSort(nums []int) bool {
  2.     set := make(map[int]int)
  4.     for _, x := range(nums) {
  5.         // 遍历所有x的primeFactor，union起来
  6.         xx := x
  7.         for p := 2; p * p <= xx; p++ {
  8.             if xx % p == 0 {
  9.                 setUnion(set, x, p)
  10.                 for xx % p == 0 {
  11.                     xx /= p
  12.                 }
  13.             }
  14.         }
  15.         // x是素数的情况下，其本身也是primeFactor
  16.         if xx != 1 {
  17.             setUnion(set, x, xx)
  18.         }
  19.     }
  21.     sorted := make([]int, len(nums))
  22.     copy(sorted, nums)
  23.     sort.Ints(sorted)
  25.     for i,_ := range(nums) {
  26.         r1, r2 := setFind(set, sorted[i]), setFind(set, nums[i])
  27.         if r1 != r2 {
  28.             return false
  29.         }
  30.     }
  31.     return true
  32. }
  34. func setFind(set map[int]int, x int) int {
  35.     if v, ok := set[x]; ok {
  36.         if v < 0 {
  37.             return x
  38.         }
  39.         set[x] = setFind(set, v)
  40.         return set[x]
  41.     } else {
  42.         set[x] = -1
  43.         return x
  44.     }
  45. }
  46. func setUnion(set map[int]int, x int, y int) {
  47.     rx := setFind(set, x)
  48.     ry := setFind(set, y)
  49.     if rx == ry {
  50.         return
  51.     }
  52.     if set[rx] < set[ry] {
  53.         set[rx] += set[ry]
  54.         set[ry] = rx
  55.     } else {
  56.         set[ry] += set[rx]
  57.         set[rx] = ry
  58.     }
  59. }

题目分析

这道题的其中一个考点，并查集，应该比较容易想到，只有当前的元素和目标的元素（排序好之后对应的元素）能够互换，才能够打到最终的目标。
那么问题转化为，union的条件是什么呢？题目中给的很直接，两个数不互质。
可是两两计算GCD，用辗转相除法，复杂度太高，这就太难办了。

那么可以找一个中间量，就是每个数的primeFactors，每个数和其所有的primeFactors都可以union，如此通过primeFactors作为桥梁，不互质的数也都union了起来，妙呀妙呀。

具体的优雅实现可能还需要一些trick，直接看代码吧。