1998. GCD Sort of an Array
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.
Constraints:
1 <= nums.length <= 3 * 10^4
2 <= nums[i] <= 10^5
Analysis:
One of the key information is that we can do the swap as many as needed, so the crux is to how to find the pair or group that can be swapped.
Let say we have three elements: A, B and C. If A and B can swap, and B and C can swap, then A, B, and C can swap in any order. So it is easy to propagate this property to groups with more than 3 elements.
Or more general: say we have a group of elements that can swap with each other. Now, we have a new element X. If X can swap with one element in the group, then X can swap with any one in the group.
So this question becomes a union-find problem: to find the connected group.
We will talk about how to find the connected group later (since it requires to consider time complexity). Suppose now we have found the connected groups. Then inside each group, we can do the swap as many as needed. This means that we can sort each group, to make sure each group is sorted, which is the best we can do with swapping. Then check the whole array, to see whether it is sorted. Return true if yes; otherwise, return false.
For example, [8, 9, 4, 2, 3]. There are two groups: [8, 4, 2] (at indexes of 0, 2 and 3) and [9, 3] (at indexes of 1 and 4). With unlimited number of swapping, the first group can be [2, 4, 8] and the second [3, 9]. Then whole array becomes [2, 3, 4, 8, 9]. So return true.
Now let us look at how to find the connected groups.
The naïve way is to find a two-layer for loop, we can check the gcd for every pair of elements. But the requires O(N^2) time complexity, where N is the number of elements. In this question, N could be as large as 10^4, so N^2 is too large. (The time complexity of gcd is considered as ~O(1) here).
We do can do faster: we can check all the prime factors of each number. If two numbers share at least one factor, then they are connected, or they belong to the same group.
The good news is that there are not many prime factors to consider. The maximum value of the elements could be 10^5, so we just need to check the prime factor in this range. A rough estimate is that there may be ~ 10% primes, so there are 10^4 prime factors.
If for each element, we scan through all the prime factors, to see whether it contains the prime factor or not, then the time complexity is O(N*10^4), which could be 10^8, which is still too large.
One improvement is that, we do not need to scan through all the prime factors. For example, if we find one number X has a prime factor p1, then we can remove all the prime factor p1 from X. Then check the X/p1 is a prime factor or not. If yes, we can stop the search; if no, we can continue the searching with X/p1 starting with prime factors larger than p1. The converging speed is much faster than scanning all the prime factors. The overall time complexity is roughly about log(10^4), for checking the prime factor for each element.
The overall time complexity is O(N*log(10^4)), which could be less than 10^6 for the largest case. And this time complexity is acceptable for the online OJ.
To make a summary about how to connected elements to a group: if one element has A, B, C, ... prime factors, then A, B, C ... prime factors are connected. Or the element can be viewed as a bridge to connected all these prime factors.
One detail for the implementation of the union-find algorithm is that the prime factor is not continuous, so a vector is not a good data structure to record the roots of the groups. Instead, a map will be used. (Why not unordered_map? since we need the prime factor to be ordered as well, to lower the time complexity in the checking prime factor step.)
See the code below:
class Solution {
public:
bool gcdSort(vector<int>& nums) {
int n = nums.size(), val = nums[0];
for(int i=0; i<n; ++i) {
val = max(nums[i], val);
}
vector<int> ps = primes(val + 1);
// for(auto &a : ps) {cout<<a<<" ";} cout<<endl;
int m = ps.size();
map<int, int> mp;
for(auto &a : ps) mp[a] = a;
vector<int> ids(n, -1);// to connect the nums to mp
for(int i=0; i<n; ++i) {
int first = -1, copy = nums[i];
for(auto &a : mp) {
// is a prime
if(mp.count(copy) > 0) {
ids[i] = find(mp, copy);
if(first != -1) mp[find(mp, copy)] = find(mp, first);
break;
}
int k = a.first;
if(k*k > copy) break;
if(copy%k == 0) {
while(copy%k == 0) copy /= k;
if(first == -1) {
first = find(mp, k);
ids[i] = first;
// cout<<i<<" "<<first<<endl;
} else {
mp[find(mp, k)] = find(mp, first);
}
}
}
}
unordered_map<int, vector<int>> ump;
for(int i=0; i<n; ++i) {
int r = find(mp, ids[i]);
ump[r].push_back(i);
}
for(auto &a : ump) {
vector<int> t;
for(auto &b : a.second) {
t.push_back(nums[b]);
}
sort(t.begin(), t.end());
int id = 0;
for(auto &b : a.second) {
nums[b] = t[id++];
}
}
for(int i=0; i<n; ++i) {
if(i+1<n && nums[i] > nums[i+1]) return false;
}
return true;
}
private:
vector<int> primes(int val) {
vector<int> res;
vector<bool> isP(val + 1, true);
for(int i=2; i<=val; ++i) {
if(isP[i]) {
res.push_back(i);
for(int j=1; j*i<=val; ++j) isP[j*i] = false;
}
}
return res;
}
int find(map<int, int>& rs, int id) {
// cout<<rs.size()<<" "<<id<<endl;
if(rs[id] != id) return rs[id] = find(rs, rs[id]);
return rs[id];
}
};
Comments
Post a Comment