题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数：
如数组{7,5,6,4}，逆序对总共有5对，{7,5}，{7,6}，{7,4}，{5,4}，{6,4}；
解题思路
暴力解法，顺序扫描整个数组，每扫描到一个数字的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成一个逆序对。假设数组中含有n个数字，由于每个数字都要和O(n)个数字作比较，因此这个算法的时间复杂度是O(n^2)。
算法图解
参考代码：
package offer
;
public class Offer51 {
public static void main(String
[] args
) {
int nums
[] = {7, 5, 6, 4};
InversePairs(nums
);
}
static void InversePairs(int nums
[]) {
for (int i
= 0; i
<nums
.length
; i
++) {
for (int j
= i
+1; j
<nums
.length
; j
++) {
if(nums
[i
]>nums
[j
]){
System
.out
.println("{"+nums
[i
]+","+nums
[j
]+"}");
}
}
}
}
}
附录
该题源码在我的 ?Github 上面！
