C++ 数组排序最小交换次数 - 代码示例及详解

//{/'title/':/'C++ 数组排序最小交换次数 - 代码示例及详解/', ///'description/':/'本文提供 C++ 代码，计算数组排序的最小交换次数。代码使用循环和 visited 数组跟踪元素访问情况，以确定最小交换次数。/', ///'keywords/':/'数组排序, 最小交换次数, C++, 代码示例, 循环, visited 数组/', ///'content/':/'//#include //<iostream//>//n//#include //<vector//>//n//#include //<algorithm//>//n//nint minSwaps(std::vector//<int//>& nums) {//n std::vector//<std::pair//<int, int//>//> arrPos(nums.size());//n for (int i = 0; i //< nums.size(); i++) {//n arrPos[i].first = nums[i];//n arrPos[i].second = i;//n }//n//n std::sort(arrPos.begin(), arrPos.end(), [](const std::pair//<int, int//>& a, const std::pair//<int, int//>& b) {//n return a.first //< b.first;//n });//n//n std::vector//<bool//> visited(nums.size(), false);//n int minSwaps = 0;//n//n for (int i = 0; i //< nums.size(); i++) {//n if (visited[i] || arrPos[i].second == i) {//n continue;//n }//n//n int cycleSize = 0;//n int j = i;//n while (!visited[j]) {//n visited[j] = true;//n j = arrPos[j].second;//n cycleSize++;//n }//n//n if (cycleSize //> 0) {//n minSwaps += cycleSize - 1;//n }//n }//n//n return minSwaps;//n}//n//nint main() {//n std::vector//<int//> nums = {4, 3, 2, 1};//n int minSwaps = minSwaps(nums);//n std::cout //<< ///'Minimum swaps required: ///' //<< minSwaps //<< std::endl;//n return 0;//n}//n//n这段代码首先创建了一个 arrPos 数组，用于存储数组元素和对应的下标。然后对 arrPos 数组进行排序，以便按升序排列元素。//n//n接下来，使用 visited 数组来跟踪是否已经访问过某个元素。然后遍历数组中的每个元素，如果已经访问过或者当前元素已经在正确的位置上，则跳过。否则，开始一个新的循环，计算循环的大小，并将循环大小减去1添加到 minSwaps 变量中。//n//n最后，返回 minSwaps 变量的值，即为最小交换次数。//n//n在上述代码中，我们使用了 std::vector 来存储数组元素和中间结果。同时，使用了标准库中的 std::sort 算法对 arrPos 数组进行排序。/'}/