分治策略-LeetCode解题java实现_x^n的时间复杂度

2.1 基本概念

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题…直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并。这个技巧是很多高校算法的基础，如排序算法（快速排序，归并排序），傅里叶变换（快速傅里叶变换）…

最优子结构是依赖特定问题和子问题的分割方式而成立的条件。各个子问题具有最优解，就能求出整个问题的最优解，此时条件成立。

比如求广州到北京的最短距离，建设这个路径必经过中间的南京，那么先把路径分割为（广州，南京）和（南京，北京）。分别求出子路径的最短距离然后再连接，就可以得到广州到北京的最短路径。因此，寻找最短路径的问题可以利用子路径的最优解获得整个问题的最优解。这样就可以证明，最短路径具有最优子结构。反之，如果不能利用子问题的最优解获得整个问题的最优解，那么这种问题就不具有最优子结构。

任何一个可以用计算机求解的问题所需要的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需要的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需要任何计算。n=2时，只要做一次比较即可排好序。n=3时只要做3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

第一：数学归纳是使用分治思想
第二：分治思想不一定使用递归结构
递归结构是循环结构的一种，也是分治思想应用最多的一种程序结构，但是不一定要使用它。
第三：分治思想的核心是“如何分”
能够把问题很棒的进行分解，也是一种能力和本事！也就是说把问题用分治法来进行解决，是算法的难点，也是重点！一方面需要经验，另一方面也需要想象力！

2.2 思想策略

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。 这种算法设计策略叫做分治法。

如果原问题可以分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分支手段，可以是子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

2.3 适用场景

分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
1
2
3
4
5
6
7

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

2.4 基本步骤

分治法在每一层递归上都有三个步骤：

step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

step3 合并：将各个子问题的解合并为原问题的解。
1
2
3
4
5

它的一般的算法设计模式如下：

Divide-and-Conquer(P)
1

1. if |P|≤n0

2. then return(ADHOC§)

3. 将P分解为较小的子问题 P1 ,P2 ,…,Pk

4. for i←1 to k

5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi

6. T ← MERGE(y1,y2,…,yk) △ 合并子问题

7. return(T)

2.5 经典示例

二分搜索
大整数乘法
Strassen矩阵乘法
棋盘覆盖
合并排序
快速排序
线性时间选择
最接近点对问题
循环赛日程表

2.6 应用实例

很多算法的思维本质上都是分治思维方式，如二分搜索、大整数乘法、合并排序、快速排序等。

实例：求x的n次幂

复杂度为O(lgn)的解法

int power(int x, int n)
{
    int result;
    if(n == 1)
        return x;
    if( n % 2 == 0)
        result = power(x, n/2) * power(x, n / 2);
    else
        result = power(x, (n+1) / 2) * power(x, (n-1) / 2);
 
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.7 练习题目

2.7.1 搜索二维矩阵II（#240）

public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0) {
                return false;
            }
            int shorterDim = Math.min(matrix.length, matrix[0].length);
            for (int i = 0; i < shorterDim; i++) {
                boolean verticalFound = binarySearch(matrix, target, i, true);
                boolean horizontalFound = binarySearch(matrix, target, i, false);
                if (verticalFound || horizontalFound) {
                    return true;
                }
            }

            return false;
        }

        public boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
            int lo = start;
            int hi = vertical ? matrix[0].length - 1 : matrix.length - 1;
            while (hi >= lo) {
                int middle = (lo + hi) / 2;
                if (vertical) {
                    if (matrix[start][middle] == target) {
                        return true;
                    } else if (matrix[start][middle] < target) {
                        lo = middle + 1;
                    } else {
                        hi = middle - 1;
                    }
                } else {
                    if (matrix[middle][start] == target) {
                        return true;
                    } else if (matrix[middle][start] < target) {
                        lo = middle + 1;
                    } else {
                        hi = middle - 1;
                    }
                }
            }
            return false;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

简单实现，时间复杂度（log(N+M)）

public boolean searchMatrix(int[][] matrix, int target) {
   // start our "pointer" in the bottom-left
    int row = matrix.length - 1;
    int col = 0;

    while (row >= 0 && col < matrix[0].length) {
        if (matrix[row][col] > target) {
            row--;
        } else if (matrix[row][col] < target) {
            col++;
        } else { // found it
            return true;
        }
    }

    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.7.2 求众数(#169)

使用哈希表存储元素出现的次数进行求解

public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i])+1);
            } else {
                map.put(nums[i], 1);
            }
        }

        int half = nums.length>>1;
        for (Integer integer : map.keySet()) {
            if (map.get(integer) > half) {
                return integer;
            }
        }

        return 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

使用分治算法求解,摘自leetcode

class Solution {
    private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    private int majorityElementRec(int[] nums, int lo, int hi) {
        // base case; the only element in an array of size 1 is the majority
        // element.
        if (lo == hi) {
            return nums[lo];
        }

        // recurse on left and right halves of this slice.
        int mid = (hi-lo)/2 + lo;
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid+1, hi);

        // if the two halves agree on the majority element, return it.
        if (left == right) {
            return left;
        }

        // otherwise, count each element and return the "winner".
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);

        return leftCount > rightCount ? left : right;
    }

    public int majorityElement(int[] nums) {
        return majorityElementRec(nums, 0, nums.length-1);
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

2.7.3 合并k个排序链表（#23）：

class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (null == lists || lists.length == 0) return null;
            return merge(lists, 0, lists.length - 1);
        }

        private ListNode merge(ListNode[] lists, int left, int right) {
            if (left == right) return lists[left];
            int middle = left + (right - left) / 2;
            ListNode leftSide = merge(lists, left, middle);
            ListNode rightSide = merge(lists, middle + 1, right);
            return mergeList(leftSide, rightSide);
        }

        private ListNode mergeList(ListNode leftSide, ListNode rightSide) {
            if (leftSide == null) return rightSide;
            if (rightSide == null) return leftSide;
            if (leftSide.val < rightSide.val) {
                leftSide.next = mergeList(leftSide.next, rightSide);
                return leftSide;
            } else {
                rightSide.next = mergeList(leftSide, rightSide.next);
                return rightSide;
            }
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27