数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

 1 class Solution {
 2 public:
 3     int InversePairs(vector<int> data) {
 4         int len = data.size();
 5         if (len <= 1)
 6         {
 7             return 0;
 8         }
 9         map<int,int> mm;
10         int tem;
11         for (int k = len -1;k > 0; --k)
12         {
13             bool done = 1;
14             for(int i = 0 ;i < k ; ++i)
15             {
16                 if(data[i] > data[i+1])
17                 {
18                     done = 0;
19                     if(mm.count(data[i])==0)
20                     {
21                         mm[data[i]] = 1;
22                     }
23                     else
24                     {
25                         ++mm[data[i]];
26                     }
27                     tem = data[i];
28                     data[i] = data[i+1];
29                     data[i+1] = tem;
30                 }
31             }
32             if(done)
33             {
34                 break;
35             }
36         }
37 
38         int sum = 0;
39         for (map<int,int>::iterator it = mm.begin();it != mm.end() ; ++ it)
40         {
41             sum += it->second;
42         }
43         return sum;
44     }
45 };