分治法

分治算法也叫分治策略，把输入分为若干个部分，递归的解每一个问题，最后将这些子问题合并成为一个全局解。

由此可以得到分治策略解决的问题特点：

该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分治模型在每一层递归上都有三个步骤：

• 分解（Divide)：将原问题分解成一系列子问题。

• 解决(Conquer)：递归的解各个子问题。若子问题足够小，则直接求解。

• 合并(Combine)：将子问题的结果合并成原问题的解。

[上文引自]： https://blog.csdn.net/disappearedgod/article/details/23599343?utm_source=copy

---

何为分治.PNG

经典例题

1、合并K个有序链表

import java.util.Arrays;

public class Solution {
    // merge two sorted listNode
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newList = new ListNode(0);
        ListNode newHead = newList;
        while (l1 != null || l2 != null) {
            if (l1 == null) {
                newHead.next = l2;
                break;
            }
            if (l2 == null) {
                newHead.next = l1;
                break;
            }

            if (l1.val < l2.val) {
                newHead.next = l1;
                l1 = l1.next;
            } else {
                newHead.next = l2;
                l2 = l2.next;
            }
            newHead = newHead.next;
        }
        return newList.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {

        final int size = lists.length;

        if (lists.length == 0) return null;
        if (lists.length == 1) return lists[0];
        if (lists.length == 2) return mergeTwoLists(lists[0],lists[1]);

        return mergeTwoLists(mergeKLists(Arrays.copyOfRange(lists, 0, size / 2)),
                mergeKLists(Arrays.copyOfRange(lists, size / 2, size)));

    }
}