【java数据结构与算法学习】小和问题、逆序对问题

秒速五厘米 2022-05-29 10:40 129阅读 0赞

小和问题和逆序对问题是可以用归并排序来实现的。

小和问题：

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

例子：

\[1,3,4,2,5\]

1左边比1小的数，没有；

3左边比4小的数，1；

4左边比4小的数，1、3；

2左边比2小的数，1；

5左边比5小的数，1、3、4、2；

所以小和为1+1+3+1+1+3+4+2 = 16

主要思想：

在归并的过程中比较，找出右边元素有多少比左边的元素大。如上面的数组，1右边有4个比1大的，那么1会出现4次。

java的实现代码：

public class SmallSum {
    	
    	public static int smallSum(int[] arr) {
    		//如果数组为空，或者数组长度小于2，直接返回
    		if (arr == null || arr.length < 2) {
    			return 0;
    		}
    		return mergeSort(arr, 0, arr.length - 1);
    	}
    	
    	public static int mergeSort(int[] arr, int L, int R) {
    		//结束条件
    		if (L == R) {
    			return 0;
    		}
    		//中点位置
    		int mid = L + ((R - L)>>1);
    		//左边产生的小和+右边产生的小和+合并产生的小和就是整个数组的小和
    		return mergeSort(arr, L, mid) 
    				+ mergeSort(arr, mid + 1, R) 
    				+ merge(arr, L, mid, R);
    	}
    	
    	public static int merge(int[] arr, int L, int mid, int R) {
    		//辅助数组
    		int[] help = new int[R - L + 1];
    		//辅助数组下标
    		int i = 0;
    		//左半边数组的指针
    		int p1 = L;
    		//右半边数组的指针
    		int p2 = mid + 1;
    		//小和
    		int res = 0;
    		//指针没有越界
    		while(p1 <= mid && p2 <= R) {
    			//如果左边指向的值小于右边指向的值，那么p1位置的值一定小于p2以后的所有值，因为是有序的，这时候产生小和
    			if (arr[p1] < arr[p2]) {
    				//计算小和
    				res = res + arr[p1] * (R - p2 + 1);
    				//排序过程
    				help[i++] = arr[p1++];
    			}else {
    				//不产生小和
    				res = res + 0;
    				//排序过程
    				help[i++] = arr[p2++];
    			}
    		}
    		//p1没有越界，说明p2越界了，将左边剩余元素拷贝到辅助数组
    		while(p1 <= mid) {
    			help[i++] = arr[p1++];
    		}
    		//p2没有越界，说明p1越界了
    		while(p2 <= R) {
    			help[i++] = arr[p2++];
    		}
    		//将辅助数组元素拷贝会原数组
    		for(int j = 0; j < help.length; j++) {
    			arr[L + j] = help[j];
    		}
    		return res;
    	}
    	public static void main(String[] args) {
    		int[] arr = {1,2,3,4,5};
    		System.out.println(smallSum(arr));
    	}
    
    }

逆序对问题：

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

主要思想：

在归并的过程中比较，找出左边有多少数比右边的数大，有则产生逆序对，打印。

java的实现代码：

public class Reverse {
    
    	public static void resverse(int[] arr) {
    		if (arr == null || arr.length < 2) {
    			return;
    		}
    		mergeSort(arr, 0, arr.length - 1);
    	}
    	
    	public static void mergeSort(int[] arr, int L, int R) {
    		if (L == R) {
    			return;
    		}
    		int mid = L + ((R - L) >> 1);
    		//打印左边合并产生的逆序对
    		mergeSort(arr, L, mid);
    		//打印右边合并产生的逆序对
    		mergeSort(arr, mid+1, R);
    		//打印整体合并产生逆序对
    		merge(arr,L,mid,R);
    	}
    	static int count = 0;
    	public static void merge(int[] arr, int L,int mid, int R) {
    		int[] help = new int[R - L + 1];
    		int i = 0;
    		int p1 = L;
    		int p2 = mid + 1;
    		
    		
    		while(p1 <= mid && p2 <= R) {
    			//如果p1元素大于p2元素，那么左半边元素一定都大于p1元素
    			if (arr[p1] > arr[p2]) {
    				//p2以后的逆序对元素全部打印出来
    				for(int j = p2 ; j<=R;j++) {
    					
    					System.out.println(arr[p1] + "" + arr[j]);
    				}
    				//计算数量
    				count +=(R - p2 + 1);
    				help[i++] = arr[p1++];
    			
    			}else {
    				
    				help[i++] = arr[p2++];
    			}
    		}
    		
    		while(p1 <= mid) {
    			help[i++] = arr[p1++];
    		}
    		while(p2 <= R) {
    			help[i++] = arr[p2++];
    		}
    		for(int j = 0; j < help.length; j++) {
    			arr[L + j] = help[j];
    		}
    	}
    	
    	public static void main(String[] args) {
    		int[] arr = {4,5,3,2,1,6};
    		resverse(arr);
    		System.out.println(count);
    	}
    }