当前位置: 代码迷 >> 综合 >> 面试题51:数组中的逆序数对
  详细解决方案

面试题51:数组中的逆序数对

热度:44   发布时间:2024-01-16 18:02:59.0

题意:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

思路:O(n2)肯定不行,用的归并排序。(树状数组也可以)

class Solution {
public:const int mod = 1000000007;int InversePairs(vector<int> data) {if (data.size() == 0)	return 0;vector<int> copy;for (int i = 0; i < data.size(); i++)copy.push_back(data[i]);return InverPairsCore(data,copy,0,data.size()-1);}int InverPairsCore(vector<int> &data, vector<int> &copy, int l, int r){if (l == r){copy[l] = data[l];return 0;}int length =(r - l)/2;int mid = (l + r) / 2;//data是原始数据 copy是修改后的数据int left = InverPairsCore(copy, data, l, mid)%mod;int right = InverPairsCore(copy, data, mid + 1, r)%mod;int lend = mid;int rend = r;int index = r;int count = 0;while (lend >= l&&rend >= mid + 1){if (data[lend] > data[rend]){copy[index--] = data[lend--];count += rend - mid;count %= mod;}else{copy[index--] = data[rend--];}}for (; lend >= l;lend--)copy[index--] = data[lend];for (; rend >= mid + 1;rend--)copy[index--] = data[rend];//cout << left + right + count << endl;return (((left + right)%mod + count)%mod)%mod;}
};

 

  相关解决方案