Algo_允许交换swap某些元素是否可以使数组有序、并查集

84 阅读 0 评论 56 点赞

我是靠谱客的博主霸气星星，最近开发中收集的这篇文章主要介绍Algo_允许交换swap某些元素是否可以使数组有序、并查集，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

catalog

添加链接描述

长度n=1e5的数组，每个元素是【2, 1e5】，你可以交换swap任意两个（不互质）的数任意次。
问是否可以将数组变为有序。

[6, 4, 12, 9] ->swap(6,4), swap(12,9) -> [4,6,9,12] true

首先看一个错误的思路：
比如对于2这个质因子，我们得到所有有2质因子的元素下标，比如是：[1, 3, 7]
即，得到[1, 7]这个区间，就说明所有有2质因子的元素都可以swap到[1,7]这个区间里。

这是错误的！！
原因很简单，只有[1,3,7] 是有2质因子，你怎么能说 [1, 2, …, 7]区间都有2质因子这显然是错误的。

两个互质的元素，虽然不能直接swap，但一定不能间接swap吗？？这个问题，是本题的核心！！

如果你的出发点，认为这是正确的。那这道题是解不出来的…

A(2*3), B(3*5), C(5*7) -> (A, C, B) -> (B, C, A) -> (C, B, A)
AC虽然不能直接swap，但可以发现，最终是可以实现： AC的swap操作的！！

只要能发现这一点，自然能想到是并查集。

即一个并查集里的元素，可以互相进行swap

首先，构造这个并查集，也是个问题！！！
如果你是想，把(A, B, C)放到一个并查集，这自然是很理想的做法。

用一个record[1e5]的数组，动态的记录： record[x]为，有x质因子的元素

if( re[_fact] != -1 ){
_u.Merge( re[_fact], i ); // re[_fact]没必要记录：所有有_fact的元素
} // 只需要记录，最近的一个元素即可。最终他们都会在同个集合里。
re[_fact] = i;

但这会多消耗1e5的空间。
其实有一种更方便的做法：我们把：A, B, C, 2, 3, 5, 7都放入集合里！
也就是，比如只有A元素，我们会把：A, 2, 3放入同个集合。
这个思路非常新颖！因为，同个集合就是说明：他们之间可以相互swap
就。虽然没有2,3,5,7这些元素，但并不影响！！

最后一步：将数组sort，得到B数组。
将A和B数组，从左到右，按位的比较，看A[i] 和 B[i] 是否在同个并查集（这个思路，也非常新颖！）

你可能会认为：
A = [7, 4, 2, 8, 2]
B = [2, 2, 4, 7, 8]
A中第一个2，和B中第一个2。如何判断是否是同一个呢？
这个问题是有必要的！！虽然他俩值相同，但是：我们的swap 针对的是：元素，而不是值
因为，所以元素是>= 2的！！即，所以相同值的元素，一定是在同一个并查集里！！！
（好像这个问题不需要考虑，因为并查集里存的是：值。而不是元素下标…）
（总之，相同值的元素，肯定可以互相的swap。因为值>=2）

还要注意一点，任意元素不一定最多swap一次！！！是可能swap多次的！！比如：a(2*3), b(3*5), c(5*7)，要想变成：c, b, a
a, b, c -> a, c, b -> b, c, a -> c, b, a

可以发现，bc是swap了2次。但因为题目说了，可以swap多次。

bool gcdSort(vector<int>& A) {
int n = A.size();
UnionFind _u(100005);
Prime_Sieve _p(100005);
for(auto i : A){
int j = i;
while(j > 1){
int _fact = _p.MaxFact[j];
_u.Merge( _fact, i );
// 这里思路很新颖
while(j % _fact == 0) j /= _fact;
}
}
vector<int> _tmp = A;
sort(_tmp.begin(), _tmp.end());
for(int i = 0; i < n; ++i){
if( _u.Find( A[i] ) != _u.Find( _tmp[i] ) ) // 这里思路很新颖！
return false;
}
return true;
}