力扣周赛置换环的应用,最少交换次数

置换环的基本概念

置换环是排列组合中的一个概念，用于描述数组元素的重排过程。当我们需要将一个数组转换为另一个数组时，可以把这个转换过程分解为若干个 “环”。每个环代表一组元素的循环交换路径。

举个简单例子

假设原数组 A = [3, 2, 1, 4]，目标数组 B = [1, 2, 3, 4]（即按升序排序）。
我们需要将 A 转换为 B，可以通过以下步骤分析：

确定每个元素的目标位置:

        1.原数组 A[0]=3，在目标数组 B 中应该位于索引 2（值为 3 的位置。

        2.原数组 A[2]=1，在目标数组 B 中应该位于索引 0（值为 1 的位置。

        3.这形成了一个环：索引 0 → 索引 2 → 索引 0，对应的值为 3 → 1 → 3

其他元素

原数组 A[1]=2 和 A[3]=4 已经在正确位置，各自形成长度为 1 的环

环的结构：

环1：0 → 2 → 0 （长度2）
环2：1 → 1 （长度1）
环3：3 → 3 （长度1）

重要结论

将一个环排序所需的最小交换次数 = 环的长度 - 1。

最少总交换次数 = 总元素数 - 环的数量

来看一道字节跳动的力扣周赛

int getSum(int x){int ret=0;while(x){ret=ret+x%10;x/=10;}return ret;}
bool comp(const pair<int,int>&p1,const pair<int,int>& p2){int num1=getSum(p1.first);int num2=getSum(p2.first);if(num1==num2){return p1.first<p2.first;}else{return num1<num2;}
}
class Solution {
public:int minSwaps(vector<int>& nums) {int len=nums.size();vector<pair<int,int>> arr;for(int i=0;i<len;i++){arr.push_back({nums[i],i});}sort(arr.begin(),arr.end(),comp);vector<int> table(nums.size());for(int i=0;i<arr.size();i++){table[arr[i].second]=i;}vector<bool> visited(len,false);int circles=0;for(int i=0;i<len;i++){if(!visited[i]){int cur=i;circles++;while(!visited[cur]){visited[cur]=true;cur=table[cur];}}}return len-circles;//元素总数-环的数量}
};