剑指Offer - 九度1348 - 数组中的逆序对
2014-01-30 23:19
4 7 5 6 4
5
题意分析：
这一题的任务是求出一个数组的逆序数，也就是只通过交换相邻元素的方式，将这个数组排成升序的最少交换次数。定义可参见百度百科：逆序数。
按照冒泡或者选择排序的方法，能很直观地求出逆序数，因为执行的操作就是交换相邻元素。但问题也很明显，效率太低无法满足时间要求。
快速排序、堆排序、归并排序应该都能对应地找出算逆序数的方法，而且时间上有优势。三者中归并排序的写法和分析方法明显比另外两者要简单，于是我选择了归并排序。
归并排序的思路很简单：
1. 排序前一半
2. 排序后一半
3. 合并两个已排序的子数组
对于a[i]~a[j]和a[j+1]~a[k]这么两段儿，如果两段都已经排好了序，且存在左半段的某个a[x]>右半段的某个a[y]的话，那么a[x]、a[x+ 1]、...、a[j]必然都大于a[y]。
按上面那种算法，一次就多了j-x+1个逆序数。这么一来，就不用一个一个地算了。要是真一个一个地算逆序数，时间复杂度必然是O(n^2)了，因为逆序数本身就是O(n^2)数量级的。
最后，别忘了用64位整数来存结果，因为10^5个数，逆序数最多可以是5*10^左右，超出了int的范围。
时间复杂度O(n * log(n))，空间复杂度O(n)。
1 // 687950 zhuli19901106 1348 Accepted 点击此处查看所有case的执行结果 1800KB 1093B 100MS 2 // 201401302316 3 #include <cstdio> 4 using namespace std; 5 6 const int MAXN = 100005; 7 int a[MAXN]; 8 int n; 9 long long int res; 10 int tmp[MAXN]; 11 12 void merge_sort_recursive(int a[], int ll, int rr) 13 { 14 if (ll >= rr) { 15 return; 16 } 17 int mm; 18 mm = (ll + rr) / 2; 19 merge_sort_recursive(a, ll, mm); 20 merge_sort_recursive(a, mm + 1, rr); 21 22 int i, j, k; 23 24 i = ll; 25 j = mm + 1; 26 k = ll; 27 while (true) { 28 if (i <= mm) { 29 if (j <= rr) { 30 if (a[i] <= a[j]) { 31 tmp[k++] = a[i++]; 32 } else { 33 tmp[k++] = a[j++]; 34 res += mm - i + 1; 35 } 36 } else { 37 tmp[k++] = a[i++]; 38 } 39 } else { 40 if (j <= rr) { 41 tmp[k++] = a[j++]; 42 } else { 43 break; 44 } 45 } 46 } 47 for (i = ll; i <= rr; ++i) { 48 a[i] = tmp[i]; 49 } 50 } 51 52 int main() 53 { 54 int i; 55 56 while (scanf("%d", &n) == 1) { 57 for (i = 0; i < n; ++i) { 58 scanf("%d", &a[i]); 59 } 60 res = 0; 61 merge_sort_recursive(a, 0, n - 1); 62 printf("%lld\n", res); 63 } 64 65 return 0; 66 }
原文：http://www.cnblogs.com/zhuli19901106/p/3536655.html