标签： 归并排序

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

JAVA 分治归并 其实挺简单的

1. 对于K个链表，可以两两合并（有点归并排序的意思）
2. 一次合并完了之后此时变成K/2个链表了，对剩下的链表继续两两合并
3. 最终全都合并到了一个链表里
4. 至于两个链表的合并过程，直接参考剑指Offer25题，比较简单算链表基本题了吧，我之前写的题解双指针合并，不如找两串珠子自己比划比划
5. 至于如何选择两两的过程可以简单设计下

//对应为k个链表在入参数组中的下标
1 [0,1],[2,3],[4,5],[6,7],[8]
2 [0,2],[4,6],[8]
4 [0,4],[8]
8 [0,8]

- 第一次 `[0,1],[2,3],[4,5],[6,7]`互相合并，结果留在第一个链表位置， `[8]`单独拉下了没关系先留着
- 第二次 `[0,2],[4,6]` 互相合并，结果存在0 , 4 位置，8继续留着，`[8]`没关系
- 第三次 再次合并`[0,4]`，`[8]`继续留着
- 最后一次合并`[0,8]`结束收工

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 1){
            return lists[0];
        }
        if (lists.length == 0){
            return null;
        }
        int dis = 1;
        while (dis < lists.length){
            //1 [0,1],[2,3],[4,5],[6,7],[8]
            //2 [0,2],[4,6],[8]
            //4 [0,4],[8]
            //8 [0,8]
            for (int i = 0; i + dis < lists.length; i += dis*2) {
                //合并两个有序链表  剑指Offer25题
                lists[i] = mergeTwoLists(lists[i],lists[i+dis]);
                lists[i+dis] = null;
            }
            dis *=2;
        }
        return lists[0];
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        ListNode head = new ListNode();
        ListNode cur = head;
        while ( l1 != null || l2 != null ){
            if (l1 == null || l2 == null){
                cur.next = l1==null?l2:l1;
                break;
            }
            if (l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        return head.next;
    }
}

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

归并，基本思路李姐

归并过程可以把代码的注释打开看下，以实际数据来解释说明下

    归并数组： [7, 6, 5, 4, 3]   [32, 11, 8, 2, 1]
    idxL:0
    idxR:3
    2
    idxL:1
    idxR:3
    2
    idxL:2
    idxR:3
    2
    idxL:3
    idxR:3
    2
    idxL:4
    idxR:3
    2
    归并结果： [32, 11, 8, 7, 6, 5, 4, 3, 2, 1]
    -----

以上数组A[7, 6, 5, 4, 3]、B[32, 11, 8, 2, 1]

1. 合并的时候，A的第0个7小于B的第0个32，结果第一位插入32，第二位11同样，第三位8同样
2. A下标0的数字7大于B下标3的数字2，此时7和后面的[2, 1]形成逆序对，逆序对个数加2
3. 6同样和后面的[2, 1]形成逆序对，逆序对个数加2
4. [5, 4, 3]也一样，逆序对分别加2
5. 而在这之前的A数组内部的逆序对，在最开始之前的时候做归并排序

    归并数组： [7]   [5]
    idxL:0
    idxR:0
    1
    归并结果： [7, 5]
    -----

以及归并数组： [7, 5] [6]和归并数组： [4] [3]，再将这两个合并归并数组： [7, 6, 5] [4, 3]，得到结果[7, 6, 5, 4, 3]，在这个过程中已经计算过了

class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        sort(nums);
        return count;
    }

    public int[] sort(int[] nums){
        if (nums.length<2){
            return nums;
        }
        int[] right = new int[nums.length/2];
        int[] left = new int[nums.length - right.length];
        System.arraycopy(nums,0,left,0,left.length);
        System.arraycopy(nums,left.length,right,0,right.length);
        left = sort(left);
        right = sort(right);
        return mergeArray(left,right);
    }

    public int[] mergeArray(int[] left, int[] right) {
        if (right.length==0){
            return left;
        }
//        System.out.println("归并数组： "+Arrays.toString(left) +"   "+ Arrays.toString(right));
        int[] arr = new int[left.length + right.length];
        int idx = -1;
        int idxL = 0;
        int idxR = 0;
        while (++idx < arr.length){
            if (idxL<left.length && (idxR>= right.length || left[idxL] > right[idxR])){
                arr[idx] = left[idxL];
                idxL++;
                count += right.length-idxR;
//                System.out.println(right.length-idxR);
            }else{
                arr[idx] = right[idxR];
                idxR++;
            }
        }
//        System.out.println("归并结果： "+Arrays.toString(arr));
//        System.out.println("-----");
        return arr;
    }
}