【LeetCode】﹝归并思想ி﹞逆序对、翻转对、排序链表、合并K个升序链表

た入场券 2022-12-30 08:29 10阅读 0赞

### 文章目录 ###

*   *  归并排序思想及其应用
     *   *  归并排序
         *   *  原地归并的抽象方法
             *  自顶向下的归并排序
             *  自底向上的归并排序
         *  归并的应用
         *   *  数组中的逆序对
             *  数组中的翻转对
         *  排序链表
         *   *  自顶向下归并
             *  纯递归版自顶向下归并
             *  自底向上归并
         *  合并K个升序链表
         *   *  【1】每次合并一个链表
             *  【2】自顶向下归并
             *  【3】自底向上归并
             *  【4】优先队列

--------------------

## 归并排序思想及其应用 ##

### 归并排序 ###

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。归并排序最吸引人的是性质是它能够保证任意长度为n的数组排序所需要的时间和**nlogn**成正比；它的主要缺点则是它所需的额外空间和n成正比

`归并排序是一种渐进最优的基于比较排序的算法`，归并排序在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是~`NlgN`

#### 原地归并的抽象方法 ####

public static void merge(int[] a, int lo, int mid, int hi) {
        
    		int i = lo, j = mid + 1;
    		for(int k = lo; k <= hi; k++) {
          //将a[lo..hi]复制到aux[lo..hi]
    			aux[k] = a[k];
    		}
    		for(int k = lo; k <= hi; k++) {
          //归并到A[lo..hi]
    			if(j > hi) {
        
    				a[k] = aux[i++];
    			}else if(i > mid) {
        
    				a[k] = aux[j++];
    			}else if(aux[i] < aux[j]) {
        
    				a[k] = aux[i++];
    			}else {
        
    				a[k] = aux[j++];
    			}
    		}
    	}

可以添加一个判断条件，若**a\[mid\] <= a\[mid + 1\]**，我们就认为数组已经是有序的并跳过merge方法。这个改动不影响排序的递归调用，但是对任意有序的子数组算法的运行时间就变为线性的了

#### 自顶向下的归并排序 ####

class Merge{
        
    	private static int[] aux;     //归并所需要的辅助数组
    	
    	public static void merge(int[] a, int lo, int mid, int hi) {
        
    		//······
    	}
    	
    	public static void sort(int[] a) {
        
    		aux = new int[a.length];      //一次性分配空间
    		sort(a, 0, a.length - 1);
    	}
    	
    	private static void sort(int[] a, int lo, int hi) {
        
    		if(lo >= hi) {
        
    			return;
    		}
    		int mid = lo + (hi - lo) / 2;
    		sort(a, lo, mid);          //将左半边排序
    		sort(a, mid + 1, hi);      //将右半边排序
    		merge(a, lo, mid, hi);     //归并结果
    	}
    	
    }

`对小规模子数组使用插入排序`

用不同的方法处理小规模问题能够改进大多数递归算法的性能，因为递归会使小规模问题中方法的调用过于频繁，所以改进对它们的处理方法就能改进整个算法。对排序来说，我们已将知道插入排序（或者选择排序）非常简单，因此很可能在小数组上比归并排序更快。使用**插入排序**处理小规模的子数组（比如长度小于15）一般可以将归并排序的运行时间缩短10%~15%

#### 自底向上的归并排序 ####

递归实现的归并排序是算法设计中**分治思想**的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。尽管我们考虑的问题是归并两个大数组，实际上我们归并的数组大多数都非常小。实现归并排序的另一种方法是先归并那些微型数组，然后再成对归并的到的子数组，如此这般，直到我们将整个数组归并在一起。这种实现方法比标准递归方法所需要的代码量更少。首先进行的是两两归并（每个元素为大小为1的数组），其次是四四归并，然后是八八归并······

public static void sort2(int[] a) {
        
    		//进行lgN次两两归并
    		int N = a.length;
    		aux = new int[N];
    		for(int sz = 1; sz < N; sz = sz + sz) {
                     //sz子数组大小
    			for(int lo = 0; lo < N - sz; lo += sz + sz) {
           //lo子数组索引
    				merge(a, lo, lo + sz - 1, Math.min(lo + 2 * sz - 1, N - 1));
    			}
    		}
    	}

当数组长度为2的幂时，自顶向下和自底向上的归并排序所用的比较次数和数组访问次数正好相同，只是顺序不同。其他时候，两种方法的比较和数组访问的次序会稍有所不同

`自底向上的归并排序比较适合用链表组织的数据`，只需要重新组织链表链接就能将链表`原地排序`

\[参考资料\]《算法》第4版

### 归并的应用 ###

#### 数组中的逆序对 ####

[LeetCode 剑指 Offer 51. 数组中的逆序对][LeetCode _ Offer 51.]

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

【解题思路】因为逆序对是左边数字大于右边数字，可用一个变量count计数逆序对数。而归并子数组时最先合并的是两个大小都为1（即只含有一个元素）的子数组，若这两个子数组的元素构成一个逆序对，则count+1；当两个子数组大小大于1时，若**左边数组元素a\[i\] > 右边数组元素a\[j\]**，那么a\[i…mid\]都大于a\[j\]，此时对于元素a\[j\]共有`mid - i + 1`个逆序对，令 **count = count + (mid - i + 1)**

merge函数相应修改如下

int count = 0;
        public static void merge(int[] a, int lo, int mid, int hi) {
        
    		//···
    		for(int k = lo; k <= hi; k++) {
          //归并到A[lo..hi]
    			//···
                if(aux[i] > aux[j]){
        
    				a[k] = aux[j++];
                    //更新逆序对数量
                    count += (mid - i + 1);
    			}
    		}
    	}

#### 数组中的翻转对 ####

[LeetCode 493. 翻转对][LeetCode 493.]

【题目】给定一个数组 nums ，如果 `i < j` 且 `nums[i] > 2 * nums[j]` 我们就将 `(i, j)` 称作一个**重要翻转对**。返回给定数组中的重要翻转对的数量

【解题思路】同上题思路一样，可在归并前使用双指针查找重要翻转对数量

int count = 0;
        public static void merge(int[] a, int lo, int mid, int hi) {
        
    		//···
            //更新重要翻转对数量
            i = mid, j = hi;
            while(i >= lo) {
        
                long v = (long)aux[i];
                if((long)aux[mid + 1] * 2 >= v) {
        
                    break;
                }
                while(j > mid && (long)aux[j] * 2 >= v) {
        
                    j--;
                }
                count += (j - mid);
                i--;
            }
            //...
    	}

### 排序链表 ###

[LeetCode 148. 排序链表][LeetCode 148.]

给你链表的头结点 `head` ，请将其按 **升序** 排列并返回 **排序后的链表**

**进阶：**

*  你可以在 `O(n log n)` 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode sortList(ListNode head) {
        
            
        }
    }

【解法一】此题用插入（或选择）排序比较简单，但时间复杂度为O（n^2），不符合题目要求

而归并排序时间复杂度为O（nlgn），下面详细讲解

#### 自顶向下归并 ####

class Solution {
        
        public ListNode sortList(ListNode head) {
        
            return sort(head, null);
        }
        private ListNode sort(ListNode head, ListNode tail) {
        
            if(head == null) return null;
            if(head.next == tail) {
        
                head.next = null;    //断开链接
                return head;
            }
            ListNode slow = head, fast = head;    //快慢指针查找链表中点
            while(fast != tail && fast.next != tail) {
        
                slow = slow.next;
                fast = fast.next.next;
            }
            //注意head, slow, tail, 递归时处理为[head, slow)和[slow, tail)
            ListNode l1 = sort(head, slow);
            ListNode l2 = sort(slow, tail);
            return merge(l1, l2);
        }
        private ListNode merge(ListNode l1, ListNode l2) {
        
            ListNode dummy = new ListNode(-1);
            ListNode p1 = l1, p2 = l2;
            ListNode temp = dummy;
            while(p1 != null && p2 != null) {
        
                if(p1.val < p2.val) {
        
                    temp.next = p1;
                    p1 = p1.next;
                }else {
        
                    temp.next = p2;
                    p2 = p2.next;
                }
                temp = temp.next;
            }
            temp.next = p1 != null ? p1 : p2;
            return dummy.next;
        }
    }

#### 纯递归版自顶向下归并 ####

【说明】此方法与上述代码思路完全相同，为了加深对指针和递归的理解，特此引入

[大神题解链接][Link 1]

class Solution {
        
        public ListNode sortList(ListNode head) {
        
            if(head == null || head.next == null) return head;
            ListNode slow = head, fast = head;
            while(fast.next != null && fast.next.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode mid = slow.next;
            slow.next = null;   //断开连接
            ListNode l1 = sortList(head);
            ListNode l2 = sortList(mid);
            return merge(l1, l2);
        }
        private ListNode merge(ListNode l1, ListNode l2) {
        
            if(l1 == null) return l2;
            if(l2 == null) return l1;
            if(l1.val < l2.val) {
        
                l1.next = merge(l1.next, l2);
                return l1;
            }else {
        
                l2.next = merge(l1, l2.next);
                return l2;
            }
        }
    }

#### 自底向上归并 ####

·········

### 合并K个升序链表 ###

[LeetCode 23. 合并K个升序链表][LeetCode 23. _K]

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            
        }
    }

#### 【1】每次合并一个链表 ####

较为简单，不做介绍

#### 【2】自顶向下归并 ####

class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            if(lists == null || lists.length == 0) return null;
            sort(lists, 0, lists.length - 1);
            return lists[0];
        }
        private void sort(ListNode[] lists, int lo, int hi) {
        
            if(lo >= hi) return;
            int mid = lo + (hi - lo) / 2;
            sort(lists, lo, mid);
            sort(lists, mid + 1, hi);
            merge(lists, lo, mid + 1);
        }
        private void merge(ListNode[] lists, int lo, int mid) {
        
            ListNode dummy = new ListNode(-1);
            ListNode p1 = lists[lo], p2 = lists[mid];
            ListNode temp = dummy;
            while(p1 != null && p2 != null) {
        
                if(p1.val < p2.val) {
        
                    temp.next = p1;
                    p1 = p1.next;
                }else {
        
                    temp.next = p2;
                    p2 = p2.next;
                }
                temp = temp.next;
            }
            temp.next = p1 != null ? p1 : p2;
            //将lists[lo]更新为合并后的链表，大于lo的置为null，每次将所有链表向左归并
            lists[lo]  = dummy.next;
            lists[mid] = null;
        }
    }

#### 【3】自底向上归并 ####

merge()函数同上

public ListNode mergeKLists(ListNode[] lists) {
        
            if(lists == null || lists.length == 0) return null;
            int N = lists.length;
            for(int sz = 1; sz < N; sz = sz + sz) {
        
                for(int lo = 0; lo < N - sz; lo += sz + sz) {
        
                    merge(lists, lo, Math.min(lo + sz, N - 1));
                }
            }
            return lists[0];
        }

#### 【4】优先队列 ####

按照每个链表的头结点大小排序

class Solution {
        
        public ListNode mergeKLists(ListNode[] lists) {
        
            if(lists == null || lists.length == 0) return null;
            Queue<ListNode> queue = new PriorityQueue<ListNode>( (o1, o2) -> {
        
                return o1.val - o2.val;
            });
            for(int i = 0; i < lists.length; i++) {
        
                if(lists[i] != null) queue.add(lists[i]);
            }
            ListNode dummy = new ListNode(-1);
            ListNode temp = dummy;
            while(!queue.isEmpty()) {
        
                ListNode node = queue.poll();
                if(node.next != null) queue.offer(node.next);
                temp.next = node;
                temp = temp.next;
            }
            return dummy.next;
        }
    }

[LeetCode _ Offer 51.]: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
[LeetCode 493.]: https://leetcode-cn.com/problems/reverse-pairs/
[LeetCode 148.]: https://leetcode-cn.com/problems/sort-list/
[Link 1]: https://leetcode-cn.com/problems/sort-list/solution/java-gui-bing-pai-xu-lian-biao-ban-by-leetcoder-yo/
[LeetCode 23. _K]: https://leetcode-cn.com/problems/merge-k-sorted-lists/