求最少需要多少次交换,能把数组排成按1-n递增的顺序,(
数组中的元素互不重复
)。
比如 初始状态 5 4 3 2 1 。交换5和1的位置 得到 1 4 3 2 5,再交换4 2的位置得到 1 2 3 4 5.只需要两次即可。
第一个数排序之后应该是1,但此时第一个位置是5,那么把5放到5应该在的位置上,
然后再把5原来位置上那个数字放到第一个位置上, 即得到 1 4 3 2 5 。此时第一个位置的数字已经找到 ,往后遍历位置2.
得到4,接下来把4放到4应该在的位置,得到 1 2 3 4 5.此时已经完全有序。
总结一下就是:
交换的时候,遍历数组,判断当前元素是否在最终位置,否则把它交换到它的最终位置,(即每次交换至少让其中一个元素被放到其最终位置),这样统计总交换次数。
int getMinSwaps(vector<int> &nums)
map<int, int>mp;
vector<int> sortedNums(nums);
sort(sortedNums.begin(), sortedNums.end());
for (int i = 0; i < sortedNums.size(); i++)mp[sortedNums[i]] = i ;//记录下标索引
int cnt = 0;
for (int i = 0; i < nums.size();i++)
if (nums[i] == sortedNums[i])continue;
swap(nums[i], nums[mp[nums[i]]]);//交换到nums[i]这个值应该在的位置
cnt++;
return cnt;
在原数组中,每个元素添加一个出边指向它最终的位置,这样画完出边后,
最少会成一个环,最多n个环。 然后原理就是, 最少交换次数=结点数n-形成的环数。
int getMinSwaps(vector<int> &nums)
{
//排序
vector<int> nums1(nums);
sort(nums1.begin(),nums1.end());
unordered_map<int,int> m;
int len = nums.size();
for (int i = 0; i < len; i++){
m[nums1[i]] = i;//建立每个元素与其应放位置的映射关系
int loops = 0;//循环节个数
vector<bool> flag(len,false);
//找出循环节的个数
for (int i = 0; i < len; i++){
if (!flag[i]){//已经访问过的位置不再访问
int j = i;
while (!flag[j]){
flag[j] = true;
j = m[nums[j]];//原序列中j位置的元素在有序序列中的位置
loops++;
return len - loops;
http://blog.csdn.net/lavorange/article/details/16971781
http://blog.csdn.net/codetz/article/details/51152407