我要评论题目
对于给定的一段正整数序列，逆序对就是序列中ai>aj，且i<j的有序对；注意序列中可能有重复数字，并分析算法的时间性能。
例如：有6个数字，分别是5,4,2,6,3,1，则逆序对数目是11。
思想
一个乱序的数组，使用归并排序的方法对其进行拆分拆分，最后剩余两个已经排好序的数组（如图1）
- 图1：
然后对两个数组再进行归并排序，排序的同时统计逆序对，比如2与1对比可以产生逆序对，则4与1、5与1也能产生逆序对，按照此思路即可统计出所有的逆序对。
代码：
package com.itwyc;
import java.util.*;
public class main {
public static long count = 0; // 逆序对个数
public static void getcount(int[] nums) {
if (nums.length > 1) {
int[] left_temp = getlefttemp(nums, 0); // 得到左边数组
int[] right_temp = getlefttemp(nums, 1);// 得到右边数组
getcount(left_temp); // 将得到的数组继续拆分
getcount(right_temp);
merge(nums, left_temp, right_temp);// 归并排序，归并的同时统计逆序对
}
}
public static int[] getlefttemp(int[] temp, int a) {
int[] current;
if (a == 0) {
current = new int[temp.length / 2];
for (int i = 0; i < temp.length / 2; i++) {
current[i] = temp[i];
}
} else {
current = new int[temp.length - temp.length / 2];
for (int i = 0; i < temp.length - temp.length / 2; i++) {
current[i] = temp[temp.length / 2 + i];
}
}
return current;
}
public static void merge(int[] nums, int[] left_temp, int[] right_temp) {
int index = 0;
int left = 0;
int right = 0;
int left_len = left_temp.length;
int right_len = right_temp.length;
while (left < left_len && right < right_len) {// 如果左边的数大于右边的数，则为逆序对
if (left_temp[left] > right_temp[right]) {
count += (left_len - left);// 如果此数为逆序对，则此数右边的数也为逆序对，因为两个数组内已经排好序
nums[index++] = right_temp[right++];
} else {
nums[index++] = left_temp[left++];
}
}
while (left < left_len) {
nums[index++] = left_temp[left++];
}
while (right < right_len) {
nums[index++] = right_temp[right++];
}
}
public static void main(string[] args) {
/**
* 逆序对问题
*/
int[] nums = {8, 7, 6, 5, 4, 3, 2, 1};
getcount(nums);
system.out.println("逆序对有" + count + "个.");
}
}
总结
以上为个人经验，希望能给大家一个参考，也希望大家多多支持代码网。
发表评论