归并排序

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param weightsA int整型一维数组 * @param weightsB int整型一维数组 * @return double浮点型 */ public double findMedianSortedArrays (int[] weightsA, int[] weightsB) { // write code here int m = weightsA.length, n = weightsB.l...

import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param lists ListNode类一维数组 * @return ListNode类 */ public ListNode mergeKLists (ListNo...

因题目要求时间复杂度为O(nlogn)，所以选用时间复杂度稳定为O(nlogn)的归并排序解决此问题。逆序对的个数其实就是在数组中值小的元素在排序过程中与位置靠前的值比它大的元素做交换位置的次数。理解了这个概念之后我们就可以在排序过程中记录这个次数，我定义了一个类属性counter来记录这个次数，在归并排序中主要步骤是合并两个有序数组，那么我们从递归过程中来看，右侧数组中值小的元素，需要排在左侧数组中值比它大的元素之前，那么左侧数组中值比它大的元素有几个，则组成的逆序对就有几个，此时counter就需要加上这个个数，我们想一下，这个值应该是代码中的length_a-a的值。解释一下，a之前的元...

public class Solution { int cnt=0; public int InversePairs(int [] array) { if(array.length != 0){ divide(array,0,array.length-1); } return cnt; } public void divide(int[] array,int start,int end){ //递归终止条件 if(start >= end) return; //取中 int mid=start+(end-start)/2; //分 divide(array,start,mid); div...

class Solution { public: long res = 0; long kmod = 1000000007; void merge(int lo, int mi, int hi, vector<int>& arr) { vector<int> b; b.assign(arr.begin() + lo, arr.begin() + mi); int lb = mi - lo; int lc = hi - mi; for (int i = 0, j = 0, k = 0; (j < lb) or (k < lc); ) { if (j < ...