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

置换环的基本概念

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

举个简单例子

假设原数组 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;//元素总数-环的数量
    }
};