编程之美-光影切割问题
package a;public class DisorderCount {/**《编程之美》“光影切割问题” * 主要是两个问题： * 1.数学公式（设定没有三条以上的直线交于同一点）： * 两条直线最多一个交点，将平面分成了4个区域； * 三条直线最多三个交点，将平面分成了7个区域； * 可以推出：N条直线 M个交点，区域数为N+M+1。 * 2.逆序数的分治求法： * 交点M的个数就是逆序数对的对数。 * 例如左边的光线顺序是(1,2,3)，右边是(3,2,1)。那么(3,1)(3,2)(2,1)共三个逆序数对，说明有三个交点。 * 归并排序来求逆序数。假设以下数据a1.a2.a3.a4分为两段，此时需要计算它们的逆序数，前半部分a1.a2，后半部分a3.a4. * （这两个部分都是已经排好序的）。如果当前a1>a3，那么可以知道a2>a3，那么当前的逆序为2.即index(a2)-index(a1)+1. * 将两个数组合并的时候，注意一下左边的数组有多少个数比右边的数组的多少数值要大 */private int count=0;public static void main(String[] args) {int[][] array={{4,3,2,1},{4,2,3,1},{1,2,3,4},{3,1,2},{2},};for(int[] each:array){DisorderCount test=new DisorderCount();int count=test.disorderCount(each);System.out.println(count);}}public int disorderCount(int[] array){if(array==null){return -1;}if(array.length<2){return 0;}disorderCountHelp(array,0,array.length-1);return count;}public void disorderCountHelp(int[] array,int start,int end){if(start<end){int mid=start+(end-start)/2;disorderCountHelp(array,start,mid);disorderCountHelp(array,mid+1,end);merge(array,start,mid,end);}}public void merge(int[] array,int start,int mid,int end){int i=start;int j=mid+1;int len=end-start+1;int[] tmp=new int[len];int k=0;while(i<=mid&&j<=end){if(array[i]<=array[j]){tmp[k++]=array[i++];}else{tmp[k++]=array[j++];count+=mid-i+1;//Each part is sorted.It means the data from a[i] to a[mid] is bigger than a[j].}}while(i<=mid){ tmp[k++]=array[i++]; } while(j<=end){ tmp[k++]=array[j++]; } for(int m=0;m<k;m++){ array[start+m]=tmp[m]; }}}