首页 > 代码库 > 数组中的逆序对(Java实现)
数组中的逆序对(Java实现)
来源:剑指offer
逆序对定义:a[i]>a[j],其中i<j
思路:利用归并排序的思想,先求前面一半数组的逆序数,再求后面一半数组的逆序数,然后求前面一半数组比后面一半数组中大的数的个数(也就是逆序数),这三个过程加起来就是整体的逆序数目了。
易错点:第二个方法在归并时,需要array的左右子数组是已排好序的数组,归并的结果是得到排好序的数组copy。因此在递归调用iPairs时,方法的前2个参数是颠倒的,这样得到的array才是排好序的。
比如第一次时用copy当辅助数组对array排序,第二次就正好反过来。
代码:
package algorithm;public class InversePairs { public static int iPairs(int[] array) { if (array == null) throw new IllegalArgumentException(); // 创建辅助数组 int length = array.length; int[] copy = new int[length]; System.arraycopy(array, 0, copy, 0, length); int numberOfInversePairs = iPairs(array, copy, 0, length - 1); return numberOfInversePairs; } /** * @author Thanos * @param array 未归并数组 * @param copy 用于存储归并后数据的数组 * @param begin 起始位置 * @param end 结束位置 * @return 逆序数 */ public static int iPairs(int[] array, int[] copy, int begin, int end) { if(begin == end) return 0; int mid = (begin + end) / 2; // 递归调用 int left = iPairs(copy, array, begin, mid); int right = iPairs(copy, array, mid + 1, end); // 归并 int i = mid, j = end, pos = end; int count = 0; // 记录相邻子数组间逆序数 while(i >= begin && j >= mid + 1) { if(array[i] > array[j]) { copy[pos--] = array[i--]; count += j - mid; } else copy[pos--] = array[j--]; } while(i >= begin) copy[pos--] = array[i--]; while(j >= mid + 1) copy[pos--] = array[j--]; return left + right + count; } public static void main(String... args) { int test[] = { 7, 5, 1, 6, 4 }; int count = iPairs(test); System.out.println(count + " "); }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。