Question

1998. GCD Sort of an Array

中文文档

Description

You are given an integer array nums, and you can perform the following operation any number of times on nums:

• Swap the positions of two elements nums[i] and nums[j] if gcd(nums[i], nums[j]) > 1 where gcd(nums[i], nums[j]) is the greatest common divisor of nums[i] and nums[j].

Return true _if it is possible to sort _nums_ in non-decreasing order using the above swap method, or _false_ otherwise._

 

Example 1:

Input: nums = [7,21,3]
Output: true
Explanation: We can sort [7,21,3] by performing the following operations:
- Swap 7 and 21 because gcd(7,21) = 7. nums = [21,7,3]
- Swap 21 and 3 because gcd(21,3) = 3. nums = [3,7,21]

Example 2:

Input: nums = [5,2,6,2]
Output: false
Explanation: It is impossible to sort the array because 5 cannot be swapped with any other element.

Example 3:

Input: nums = [10,5,9,3,15]
Output: true
We can sort [10,5,9,3,15] by performing the following operations:
- Swap 10 and 15 because gcd(10,15) = 5. nums = [15,5,9,3,10]
- Swap 15 and 3 because gcd(15,3) = 3. nums = [3,5,9,15,10]
- Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9,10,15]

 

Constraints:

• 1 <= nums.length <= 3 * 104
• 2 <= nums[i] <= 105

Solutions

Solution 1

class Solution:
  def gcdSort(self, nums: List[int]) -> bool:
    n = 10**5 + 10
    p = list(range(n))
    f = defaultdict(list)
    mx = max(nums)
    for i in range(2, mx + 1):
      if f[i]:
        continue
      for j in range(i, mx + 1, i):
        f[j].append(i)

    def find(x):
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    for i in nums:
      for j in f[i]:
        p[find(i)] = find(j)

    s = sorted(nums)
    for i, num in enumerate(nums):
      if s[i] != num and find(num) != find(s[i]):
        return False
    return True

class Solution {
  private int[] p;

  public boolean gcdSort(int[] nums) {
    int n = 100010;
    p = new int[n];
    Map<Integer, List<Integer>> f = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    int mx = 0;
    for (int num : nums) {
      mx = Math.max(mx, num);
    }
    for (int i = 2; i <= mx; ++i) {
      if (f.containsKey(i)) {
        continue;
      }
      for (int j = i; j <= mx; j += i) {
        f.computeIfAbsent(j, k -> new ArrayList<>()).add(i);
      }
    }
    for (int i : nums) {
      for (int j : f.get(i)) {
        p[find(i)] = find(j);
      }
    }
    int[] s = new int[nums.length];
    System.arraycopy(nums, 0, s, 0, nums.length);
    Arrays.sort(s);
    for (int i = 0; i < nums.length; ++i) {
      if (s[i] != nums[i] && find(nums[i]) != find(s[i])) {
        return false;
      }
    }
    return true;
  }

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

class Solution {
public:
  vector<int> p;

  bool gcdSort(vector<int>& nums) {
    int n = 100010;
    p.resize(n);
    for (int i = 0; i < n; ++i) p[i] = i;
    int mx = 0;
    for (auto num : nums) mx = max(mx, num);
    unordered_map<int, vector<int>> f;
    for (int i = 2; i <= mx; ++i) {
      if (!f[i].empty()) continue;
      for (int j = i; j <= mx; j += i) f[j].push_back(i);
    }
    for (int i : nums) {
      for (int j : f[i]) p[find(i)] = find(j);
    }
    vector<int> s = nums;
    sort(s.begin(), s.end());
    for (int i = 0; i < nums.size(); ++i) {
      if (s[i] != nums[i] && find(s[i]) != find(nums[i])) return false;
    }
    return true;
  }

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

var p []int

func gcdSort(nums []int) bool {
  n := 100010
  p = make([]int, n)
  for i := 0; i < n; i++ {
    p[i] = i
  }
  mx := 0
  for _, num := range nums {
    mx = max(mx, num)
  }
  f := make([][]int, mx+1)
  for i := 2; i <= mx; i++ {
    if len(f[i]) > 0 {
      continue
    }
    for j := i; j <= mx; j += i {
      f[j] = append(f[j], i)
    }
  }
  for _, i := range nums {
    for _, j := range f[i] {
      p[find(i)] = find(j)
    }
  }
  s := make([]int, len(nums))
  for i, num := range nums {
    s[i] = num
  }
  sort.Ints(s)
  for i, num := range nums {
    if s[i] != num && find(s[i]) != find(num) {
      return false
    }
  }
  return true
}

func find(x int) int {
  if p[x] != x {
    p[x] = find(p[x])
  }
  return p[x]
}