求一个序列排好序的最少交换次数

淩亂°似流年 2022-02-24 03:26 174阅读 0赞

问题描述：

给定一个序列， a1,a2,a3....an,将其按从小到大排列，那么最少的交互次数是多少？

例如 2 1 3 到 1 2 3的最少交换次数是1,3 1 2 的最少交换次数是2.

思路：将数组sort，记录下对应的位置。

在原数组中，每个元素添加一个出边指向它最终的位置，这样画完出边后，

最少会成一个环，最多n个环。 然后原理就是， **最少交换次数=结点数n-形成的环数**。

代码：

int getMin(vector<int> &vec1){
        vector<int> vec(vec1);
        map<int,int> mp;
        sort(vec.begin(),vec.end());
        int kk=0;
        for(auto &v: vec){
            mp[v]=kk++;
        }
        int cnt=0;
        vector<bool> flag(vec.size(),false);
        int len=vec.size();
        for(int i=0;i<len;i++){
            if(!flag[i]){
                int j=i;
                while(!flag[j]){
                    flag[j]=true;
                    j = mp[vec1[j]];
                }
                cnt++;
            }
        }
        return len-cnt;
    }

例题：[https://codeforces.com/group/wMJANuSahq/contest/102148/problem/E][https_codeforces.com_group_wMJANuSahq_contest_102148_problem_E]

[https_codeforces.com_group_wMJANuSahq_contest_102148_problem_E]: https://codeforces.com/group/wMJANuSahq/contest/102148/problem/E

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关华为OD机试 - 最少交换次数（C语言）

题目描述给出数字K,请输出所有结果小于K的整数组合到一起的最少交换次数。组合一起是指满足条件的数字相邻，不要求相邻后在数组中的位置。数据范围： \-100 <

本是古典何须时尚/ 2024年03月27日 19:24/ 0 赞/ 90 阅读

相关【第22题】有一个已经排好序的数组

回城传送–》[《JAVA筑基100例》][JAVA_100] 文章目录零、前言一、题目描述二、解题思路三、代码详解解

绝地灬酷狼/ 2023年10月07日 18:37/ 0 赞/ 20 阅读

相关 LeetCode - 2134 最少交换次数来组合所有的 1 II

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [2134. 最少交换次数来组合所有的 1

谁借莪１个温暖的怀抱￠/ 2023年09月24日 13:39/ 0 赞/ 92 阅读

相关 LeetCode - 1151 最少交换次数来组合所有的1

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [1151. 最少交换次数来组合所有的 1

逃离我推掉我的手/ 2023年09月24日 13:39/ 0 赞/ 59 阅读

相关华为OD机试 - 最少交换次数（Java & JS & Python）

目录题目描述输入描述输出描述用例题目解析算法源码 -------------------- 题目描述给出数字K,请输出所有结果小于K的整数组

骑猪看日落/ 2023年09月24日 12:54/ 0 赞/ 149 阅读

相关交换排序（冒泡排序、快速排序）

/ 交换排序：冒泡排序、选择排序（把字符串数组转换为int数组后排序） @author zxc / public

短命女/ 2022年08月13日 18:31/ 0 赞/ 35 阅读

相关 Ultra-QuickSort 求最小交换次数即求逆序对数树状数组+离散化

首先介绍一下树状数组树状数组(binary indexed tree)，是一种设计新颖的数组结构，它能够高效地获取数组中连续n个数的和。概括说，树状数组通常用于解决以下问题

素颜马尾好姑娘i/ 2022年06月13日 08:45/ 0 赞/ 252 阅读

相关交换排序之《冒泡排序》

距离上次写博客已经过去20天了，卤煮没有偷懒，而是毕业找到了新的工作。于是从帝都来到了夏天不冷、冬天也不冷的厦门，2000多公里的路程，不远千里，公司的环境超级棒！哈哈！开

系统管理员/ 2022年05月16日 10:52/ 0 赞/ 145 阅读

相关交换排序之《快速排序》

快速排序，见名知意肯定是比较快。据实验所要排序的序列越乱，快速排序的效率越高！也是一种不稳定的排序！快速排序基本思想：通过一轮的排序将序列分割成独立的两部分，其中前一部分序

逃离我推掉我的手/ 2022年05月14日 03:17/ 0 赞/ 132 阅读

相关求一个序列排好序的最少交换次数

问题描述：给定一个序列， a1,a2,a3....an,将其按从小到大排列，那么最少的交互次数是多少？例如 2 1 3 到 1 2 3的最少交换次数是1,3 1 2 的

淩亂°似流年/ 2022年02月24日 03:26/ 0 赞/ 175 阅读