数据结构与算法Java版-逆序对问题（java数组逆序输出）

数据结构与算法Java版-逆序对问题（java数组逆序输出）

逆序对问题

在一个数组中，左边的数如果比右边的数大，则这两个构成一个逆序对，请打印所有的逆序对数量

思路：逆序对数量的问题可以使用归并排序的思路，只不过需要按照从大到小的顺序排列，在归并的时候计算逆序对数，java实现如下：

package problem;public class ReverseOrderPair { // 在一个数组中，左边的数如果比右边的数大，则这两个构成一个逆序对，请打印所有的逆序对数量 public static int merge(int[] arr,int left,int mid,int right) { int num=0; int p1=left; int p2=mid+1; int[] arr_new=new int[right-left+1]; int i=0; while(p1<=mid && p2<=right) { num+=arr[p1]>arr[p2]?(right-p2+1):0; arr_new[i++]=arr[p1]>arr[p2]?arr[p1++]:arr[p2++]; } while(p1<=mid) { arr_new[i++]=arr[p1++]; } while(p2<=right) { arr_new[i++]=arr[p2++]; } for(int j=0;j>1); return getReverseOrderPairNum(arr,left,mid)+getReverseOrderPairNum(arr,mid+1,right)+merge(arr,left,mid,right); } public static void printArray(int[] arr) { for(int elem:arr) { System.out.print(elem+"\t"); } System.out.println(); } public static void main(String[] args) { int[] arr={6,1,3,4,2,5,0}; int sum=getReverseOrderPairNum(arr,0,arr.length-1); System.out.println(sum); printArray(arr); }}

执行结果如下：

136 5 4 3 2 1 0

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。