题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。例如,在数组{7, 5, 6, 4}中,一共存在5个逆序对,分别是(7, 6)(7,5)(7,4)(6, 4)和(5, 4)。
思路:
代码实现:
package Question51; import java.util.Arrays; public class T01 { static int count; public static void main(String[] args) { int[] arr = {7, 5, 6, 4}; System.out.println(solve(arr)); } public static int solve(int[] arr) { if(arr == null && arr.length == 0) return count; int left = 0, right = arr.length-1; divide(arr, left, right); return count; } public static void divide(int[] arr, int left, int right) { //说明只有1个元素 if(left == right) return ; int mid = left + (right - left) / 2; divide(arr, left, mid); divide(arr, mid+1, right); merge(arr, left, mid, mid+1, right); } public static void merge(int[] arr, int left1, int right1, int left2, int right2) { int[] arr1 = Arrays.copyOfRange(arr, left1, right1+1); int[] arr2 = Arrays.copyOfRange(arr, left2, right2+1); int p1 = arr1.length - 1, p2 = arr2.length - 1, p3 = right2; while(p1 >= 0 && p2 >= 0) { if(arr1[p1] > arr2[p2]) { count += p2 + 1; arr[p3--] = arr1[p1--]; } else arr[p3--] = arr[p2--]; } while(p1 >= 0) arr[p3--] = arr1[p1--]; while(p2 >= 0) arr[p3--] = arr2[p2--]; } }