转成有序数组的最少交换次数

2023-10-12 13:24| 来源: 网络整理| 查看: 265

问题描述：

第一题：现在想通过交换相邻元素的操作把一个给定序列交换成有序，最少需要交换的次数是多少？比如3 1 2 4 5需要最少交换2次。

答案：需要交换的最少次数为该序列的逆序数。

证明：可以先将最大数交换到最后，由于是相邻两个数交换，需要交换的次数为最大数后面的数的个数（可以看做是最大数的逆序数），然后，交换过后，去除最大数，再考虑当前最大数也需要其逆序数次交换。则每个数都需要交换其逆序数次操作，则总最少交换次数为序列总体的逆序数。

class Solution { public: int minSwap(vector&nums) { if(nums.empty()||nums.size()==1)return 0; int res=0; for(int i=0;iA[i-1],B[i]>B[i-1]因为只要保持就可以了，所以keep[i]=keep[i-1]，但是如果要交换，那就比swap[i-1]还多了个第i个元素的代价，也就是swap[i]=swap[i-1]+1.

二、A[i]>B[i-1] 而且B[i]>A[i-1]这种情况满足了“是不是我可以通过交换使得满足条件”，值得一提的是这两个条件应该同时判断，因为谁也不知道那种情况下会有更小的代价。但是如果交换就会是keep[i-1]+1的代价（因为实际上就是翻转了第i个再加上让前i-1个保持的代价），同理keep[i]此时等于swap[i-1]因为不翻转这个，但要翻转前i个。代码：

//dp1[i]表示在不交换A[i]和B[i]的情况下，使得A的前i + 1个元素和B的前i + 1个元素严格递增的最小交换次数； //dp2[i]表示在交换A[i]和B[i]的情况下，使得A的前i + 1个元素和B的前i + 1个元素严格递增的最小交换次数。 class Solution { public: int minSwap(vector& A, vector& B) { int length = A.size(); vector dp1(length, INT_MAX); vector dp2(length, INT_MAX); dp1[0] = 0; dp2[0] = 1; for(int i=1; iA[i-1]&&B[i]>B[i-1]){ dp1[i] = dp1[i-1]; dp2[i] = dp2[i-1]+1; //需要交换因此+1 } if(B[i]>A[i-1]&&A[i]>B[i-1]){ dp1[i] = min(dp1[i], dp2[i-1]); dp2[i] = min(dp2[i], dp1[i-1]+1); //如果dp1[i - 1] + 1 < dp2[i]，那么说明在维持第i - 1对元素的次序的情况下，交换第i对元素可以达到更优解 } } return min(dp1.back(), dp2.back()); } };

【本文地址】

公司简介

联系我们