剑指Offer - 九度1348 - 数组中的逆序对

剑指Offer - 九度1348 - 数组中的逆序对
2014-01-30 23:19
题目描述:
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
输入:
每个测试案例包括两行:
第一行包含一个整数n,表示数组中的元素个数。其中1 <= n <= 10^5。
第二行包含n个整数,每个数组均为int类型。
输出:
对应每个测试案例,输出一个整数,表示数组中的逆序对的总数。
样例输入:
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)。
剑指Offer - 九度1348 - 数组中的逆序对
 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 }
剑指Offer - 九度1348 - 数组中的逆序对

剑指Offer - 九度1348 - 数组中的逆序对

上一篇:unity3D对象的显示和隐藏


下一篇:数据库连接&数据库进程&数据库操作