题目描述：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
解题思路：
一开始一头雾水，后面想到了使用归并排序的思想，其实有多少个逆序对，就是归并排序的时候，后面的数要超越前面多少个，嗯，好像不是很好说，要不然直接看代码吧。还要注意，题目当中说要输出取模的结果，这说明数据可能非常大，所以如果只是单纯的在最后取模的话可能还是无法避免数据太大的影响，所以我们在每次更新count的时候就对其进行取模运算。
刚好又练习了一遍归并排序，记录一下
public class Solution {
int count;
public int InversePairs(int [] array) {
count = 0;
if(array != null){
divPairs(array, 0, array.length-1);
}
return count%1000000007;
}
public void divPairs(int[] array, int start, int end){
if(start >= end)
return;
int mid = (start + end)>>1;
divPairs(array, start, mid);
divPairs(array, mid+1, end);
mergePairs(array, start, mid, end);
}
public void mergePairs(int[] array, int start, int mid, int end){
int i = start, j = mid+1, k = 0;
int[] temp = new int[end-start+1];
while(i <= mid && j <= end){
if(array[i] <= array[j]){
temp[k++] = array[i++];
}else{
temp[k++] = array[j++];
count += mid - i + 1;
count %= 1000000007;
}
}
while(i <= mid){
temp[k++] = array[i++];
}
while(j <= end){
temp[k++] = array[j++];
}
for(int x = 0; x < temp.length; x++){
array[start+x] = temp[x];
}
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对，例如在数组｛7，5，6，4｝中，一共存在5对逆序对，分别是｛7，6｝，｛7，5｝，｛7，4｝，｛6，4｝，｛5，4｝。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。，即输出P%1000000007。
代码
解法一
暴力简单低效，不会改变原数组
public static int inversePairs(int[] array) {
if (array == null || array.length < 2) {
return 0;
}
int count = 0;
for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
count++;
}
}
}
return count % 1000000007;
}
解法二
利用数组的归并排序，高效，但是会改变原数组
public static int inversePairs2(int[] array) {
if (array == null || array.length < 2) {
return 0;
}
int count = mergeSort(array, 0, array.length - 1);
return count % 1000000007;
}
private static int mergeSort(int[] array, int start, int end) {
if (start >= end) {
return 0;
}
// 找到数组的中点，分割为两个子数组，递归求解
int middle = (start + end) / 2;
int left = mergeSort(array, start, middle);
int right = mergeSort(array, middle + 1, end);
// 存储归并后的数组
int[] copy = new int[array.length];
System.arraycopy(array, start, copy, start, end - start + 1);
// 从两个子数组的尾部开始遍历
int i = middle;
int j = end;
int copyIndex = end;
// 记录逆序对的数量
int count = 0;
while (i >= start && j >= middle + 1) {
// 数组是升序的
// 如果左边数组比右边数组大，则将大的放入存储数组中
// 并且累加逆序对，应为是有序的，所以左边数组的第i个元素比第j个及其之前的数都大
if (array[i] > array[j]) {
copy[copyIndex--] = array[i--];
count += (j - middle);
} else {
copy[copyIndex--] = array[j--];
}
}
// 将子数组剩余的部分一次写入归并后的存储数组
while (i >= start) {
copy[copyIndex--] = array[i--];
}
while (j >= middle + 1) {
copy[copyIndex--] = array[j--];
}
// 将本次两个子数组的合并写入原数组中
for (int k = start; k <= end ; k++) {
array[k] = copy[k];
}
return left + right + count;
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

php实现数组中的逆序对(归并排序实现：排序 辅助数组)
一、总结
这题用归并排序  线段树   树状数组 等操作的复杂度应该都是小于n方的
二、php实现数组中的逆序对
题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
示例1
输入
1,2,3,4,5,6,7,0
输出
7
三、代码
思路分析：
看到这个题目，我们的第一反应是顺序扫描整个数组。每扫描到一个数组的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成了一个逆序对。假设数组中含有n个数字。由于每个数字都要和O(n)这个数字比较，因此这个算法的时间复杂度为O(n^2)。
我们以数组{7,5,6,4}为例来分析统计逆序对的过程。每次扫描到一个数字的时候，我们不拿ta和后面的每一个数字作比较，否则时间复杂度就是O(n^2)，因此我们可以考虑先比较两个相邻的数字。
(a) 把长度为4的数组分解成两个长度为2的子数组；
(b) 把长度为2的数组分解成两个成都为1的子数组；
(c) 把长度为1的子数组 合并、排序并统计逆序对 ；
(d) 把长度为2的子数组合并、排序，并统计逆序对；
在上图(a)和(b)中，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5，因此(7,5)组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对(6,4)。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组 排序 如上图(c)所示， 以免在以后的统计过程中再重复统计。
接下来我们统计两个长度为2的子数组子数组之间的逆序对。合并子数组并统计逆序对的过程如下图如下图所示。
我们先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数，如下图(a)和(c)所示。如果第一个数组的数字小于或等于第二个数组中的数字，则不构成逆序对，如图b所示。每一次比较的时候，我们都把较大的数字从后面往前复制到一个辅助数组中，确保
辅助数组(记为copy) 中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。
过程：先把数组分割成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。如果对排序算法很熟悉，我们不难发现这个过程实际上就是归并排序。参考代码如下：
1 classSolution {2 public:3     int InversePairs(vectordata) {4        int length=data.size();5         if(length<=0)6             return 0;7        //vector copy=new vector[length];
8        vectorcopy;9        for(int i=0;i
13        return count%1000000007;14 }15     long long InversePairsCore(vector &data,vector &copy,int start,intend)16 {17        if(start==end)18 {19             copy[start]=data[start];20             return 0;21 }22        int length=(end-start)/2;23        long long left=InversePairsCore(copy,data,start,start+length);24        long long right=InversePairsCore(copy,data,start+length+1,end);25 26        int i=start+length;27        int j=end;28        int indexcopy=end;29        long long count=0;30        while(i>=start&&j>=start+length+1)31 {32              if(data[i]>data[j])33 {34                   copy[indexcopy--]=data[i--];35                   count=count+j-start-length;          //count=count+j-(start+length+1)+1;
36 }37              else
38 {39                   copy[indexcopy--]=data[j--];40 }41 }42        for(;i>=start;i--)43            copy[indexcopy--]=data[i];44        for(;j>=start+length+1;j--)45            copy[indexcopy--]=data[j];46        return left+right+count;47 }48 };

    
php实现数组中的逆序对（归并排序实现：排序 辅助数组）
一、总结
这题用归并排序  线段树   树状数组 等操作的复杂度应该都是小于n方的
 
二、php实现数组中的逆序对
题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5

示例1


输入

1,2,3,4,5,6,7,0



输出

7





 
三、代码
思路分析： 
看到这个题目，我们的第一反应是顺序扫描整个数组。每扫描到一个数组的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成了一个逆序对。假设数组中含有n个数字。由于每个数字都要和O(n)这个数字比较，因此这个算法的时间复杂度为O(n^2)。
我们以数组{7,5,6,4}为例来分析统计逆序对的过程。每次扫描到一个数字的时候，我们不拿ta和后面的每一个数字作比较，否则时间复杂度就是O(n^2)，因此我们可以考虑先比较两个相邻的数字。
  
 


  (a) 把长度为4的数组分解成两个长度为2的子数组；  
   (b) 把长度为2的数组分解成两个成都为1的子数组；   
    (c) 把长度为1的子数组  合并、排序并统计逆序对  ；    
   (d) 把长度为2的子数组合并、排序，并统计逆序对；   
     在上图（a）和（b）中，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对（6,4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组  排序  如上图（c）所示，  以免在以后的统计过程中再重复统计。     
     接下来我们统计两个长度为2的子数组子数组之间的逆序对。合并子数组并统计逆序对的过程如下图如下图所示。   
    我们先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数，如下图（a）和（c）所示。如果第一个数组的数字小于或等于第二个数组中的数字，则不构成逆序对，如图b所示。每一次比较的时候，我们都把较大的数字从后面往前复制到一个辅助数组中，确保 辅助数组（记为copy） 中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。   
   
 



   过程：先把数组分割成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。如果对排序算法很熟悉，我们不难发现这个过程实际上就是归并排序。参考代码如下：


 1 class Solution {
 2 public:
 3     int InversePairs(vector<int> data) {
 4        int length=data.size();
 5         if(length<=0)
 6             return 0;
 7        //vector<int> copy=new vector<int>[length];
 8        vector<int> copy;
 9        for(int i=0;i<length;i++)
10            copy.push_back(data[i]);
11        long long count=InversePairsCore(data,copy,0,length-1);
12        //delete[]copy;
13        return count%1000000007;
14     }
15     long long InversePairsCore(vector<int> &data,vector<int> &copy,int start,int end)
16     {
17        if(start==end)
18           {
19             copy[start]=data[start];
20             return 0;
21           }
22        int length=(end-start)/2;
23        long long left=InversePairsCore(copy,data,start,start+length);
24        long long right=InversePairsCore(copy,data,start+length+1,end); 
25         
26        int i=start+length;
27        int j=end;
28        int indexcopy=end;
29        long long count=0;
30        while(i>=start&&j>=start+length+1)
31           {
32              if(data[i]>data[j])
33                 {
34                   copy[indexcopy--]=data[i--];
35                   count=count+j-start-length;          //count=count+j-(start+length+1)+1;
36                 }
37              else
38                 {
39                   copy[indexcopy--]=data[j--];
40                 }          
41           }
42        for(;i>=start;i--)
43            copy[indexcopy--]=data[i];
44        for(;j>=start+length+1;j--)
45            copy[indexcopy--]=data[j];       
46        return left+right+count;
47     }
48 };

 

 

转载于:https://www.cnblogs.com/Renyi-Fan/p/9082224.html