题意理解：对于一个从1到n的有序数组，每个位置上的元素可以和位于它前面的元素交换一次，每个元素最多可以有2次这样向前交换的机会，问对于输入的数组排列是否可以通过这样的操作得到，如果可以得到，最少需要多少次这样的交换操作。
分析：初始状态下，从1到n的有序数组是没有逆序对的，之后为了形成输入的a[0]，a[1]，…，a[n-1]这样的排列，从a[0]开始看，a[0]后面有多少个比a[0]小的元素，a[0]就必须得向前交换多少次才能到达当前位置(在a[0]后面的，且比a[0]大的，本来从初始状态开始就排在a[0]后面，根本不需要a[0]和他们去交换)。而位于a[0]后面且比a[0]小的元素个数其实就是输入排列从a[0]开始算的逆序数。同样的对a[1]，a[2]，…，a[n-1]也都是如此，他们需要向前交换的次数都是各自的逆序数。因此对于输入的数组排列，其逆序个数就是从有序数组变为这个排列需要的交换次数。
只是这个题目额外多了1个限制，那就是要求对于输入的排列中的每个a[i]，位于其后的a[i+1]，a[i+2]，…，a[n-1]中小于a[i]的不能超过2个，也就是a[i]最多是经过两次向前交换到达当前位置的(但是a[i]是可以经过超过2次向后交换到达当前位置，比如输入排列是2，3，…，n-1，1的话，那么1就是经过n-1次向后交换到达了最后一个位置)。
所以，按照统计逆序数的思路来写，可以这样：
void minimumBribes(vector<int> q) {
int swap = 0;
int len = q.size();
for (int i = 0; i < len; i++) {
int innerSwap = 0;
for (int j = i + 1; j < len; j++) {
if (q[i] > q[j]) {
++innerSwap;
++swap;
}
if (innerSwap > 2) {
cout << "Too chaotic" << endl;
return;
}
}
}
cout << swap << endl;
}但是这样会超时。看了讨论区的回答，才明白可以根据每个元素可以最多向前交换2次进行优化：
- 对于输入的排列a[0]，a[1]，…，a[n-1]中的a[k]，a[k]最多经历过2次向前交换来到当前位置，所以a[k]最多是(k+1)+2交换上来的，(k+1)是因为初始状态下索引为k的这个位置上放的是k+1，+2代表a[k]由初始状态下的索引为k的元素后面的第2个元素向前交换而来；
- 数逆序数时，如果向前面思路那样从a[k]开始数后面比a[k]小的个数的话，那么要每次枚举a[k]后面的所有元素，因为比a[k]小的元素被交换到a[k]后面之后，可以再被交换到任何位置；按照讨论区的思路可以从a[n-1]开始枚举a[k]前面比a[k]大的数。a[k]在初始状态位于索引为a[k]-1的位置，由于每个元素至多向前交换2次，所以比a[k]大的元素最多被交换到a[k]-2的位置，这样就可以只枚举索引为max(0,a[k]-2)到k-1这个范围里有多少个数比a[k]大。
void minimumBribes(vector<int> q) {
int swap = 0;
int len = q.size();
for (int i = 0; i < len; i++) {
if (q[i] > i+3) {
cout << "Too chaotic" << endl;
return;
}
for (int j = max(0, q[i]-2); j < i; j++) {
if (q[j] > q[i]) {
++swap;
}
}
}
cout << swap << endl;
}复杂度：由于每个逆序对加了1，所以至少是O(逆序数)。
官方解法
更一般的解法
如果没有只能向前交换2次的限制，这个问题就是更一般的求逆序数的问题。
用归并排序求解
将输入的排列递归地分为两部分计算逆序数，输入排列的逆序数等于前半部分数组内部的逆序数加后半部分内部的逆序数，以及跨越了前/后半部分的逆序对的个数。前/后办部分内部的逆序数是子问题，递归求解。而跨越了前/后半部分的逆序对的个数则可以在merge前/后半部分的时候计算，因为merge的时候后半部分是有序的，所以可以很容易统计后半部分有多少个数比前半部分里的某个数小。
写归并排序时，也需要思考如何让归并排序的代码更简洁和高效。
long count_inversion(vector<int> &arr, int start, int end, vector<int> &tmp_arr) {
if (end <= start + 1) {
return 0;
}
long res = 0;
int mid = (start + end) / 2;
vector<int> &l_arr = tmp_arr;
int l_i = start;
int r_i = mid;
int k = start;
res += count_inversion(arr, start, mid, tmp_arr);
res += count_inversion(arr, mid, end, tmp_arr);
for (int i = start; i < mid; i++) {
l_arr[i] = arr[i];
}
while (l_i < mid && r_i < end) {
if (l_arr[l_i] <= arr[r_i]) {
arr[k++] = l_arr[l_i++];
res += (r_i - mid);
} else {
arr[k++] = arr[r_i++];
}
}
while (l_i < mid) {
arr[k++] = l_arr[l_i++];
res += (r_i - mid);
}
while (r_i < end) {
arr[k++] = arr[r_i++];
}
return res;
}
/*
* Complete the 'countInversions' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts INTEGER_ARRAY arr as parameter.
*/
long countInversions(vector<int> arr) {
vector<int> tmp_arr(arr.size());
return count_inversion(arr, 0, arr.size(), tmp_arr);
}用线段树或者树状数组求解
树状数组
树状数组算是线段树的一个子类吧，由于代码好写受到大家青睐。
觉得知乎这个回答讲得最好，树状数组也是将原数组分层次划分为了多个区间，划分的思路就是按照每层整合两个下层结点的方案，把这个数组一层一层往上整合，为了节省空间，删去了不必要的结点，将结点数压缩到与数组长度相同。再具体的特性和理解就去看这个知乎回答了吧。
利用树状数组去逆序数的思路：对于输入的排列a[0]，…，a[n-1]，假设数组元素的取值范围是1到m，那么构造一个新的数组b[1]，…，b[m]，以及相应的树状数组c[1]，…，c[m]。数组b[1]，…，b[m]开始都初始化为0，b[i]代表数组a[0]，…，a[n-1]中值为b[i]的数的个数。c[i]则是树状数组覆盖的数组b对应区间的和。计算逆序数算法的工作流程就是：
- 枚举a[0]，…，a[n-1]；
- 要计算在排列中a[i]前面有多少个数大于a[i]，等价于要算a[i]前面有多少个数小于等于a[i](先不考虑排列中存在元素相等的情况)，因为a[i]前面有i个元素，减去a[i]前面小于a[i]的元素个数就是a[i]前面大于a[i]的元素个数。而b[1]，…，b[a[i]]的和就是a[i]前面小于等于a[i]的元素个数，而这个和就正好利用树状数组c来求。
- 用枚举的a[i]去更新数组b和c，让b[a[i]]加1,表示a[i]这个值出现次数加1，同时更新对应的树状数组c。
- 对于所有的a[i]求出了a[i]前面大于a[i]的元素个数，再求和即是输入排列的逆序数。
需要考虑的问题：
离散化：输入排列中每个元素的取值范围可能很大，或者是负数，浮点数，这个时候需要将原来的数组换成每个数在数组中的排序位置，不然数组b的大小可能会很离谱。离散化的方式不必像上面简书那篇博客一样先排序，然后再对每个元素查找排序后的位置，而是可以用一个struct {int val, int index}的结构体来代替原来的元素进行排序，然后再遍历排序后的结构体数组，更新结构体内部的index即可，这样就免去了对每个元素查找排序后的位置的查找时间。
近期评论