常用算法总结之分治算法

分治法思想

将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时都有三个步骤：

• 分解原问题为若干个子问题，这些子问题是原问题规模较小的实例。
• 解决这些子问题，递归地求解各子问题。然而，若子问题规模足够小，则直接求解。
• 合并这些子问题的解成原问题的解。

归并排序中的分治模式

1. 分解：分解待排序的n个元素的序列成各具n/2各元素的两个子序列。
2. 解决：使用归并排序递归地排序两个子序列。
3. 合并：合并两个已排序的子序列以产生已排序的答案。

我们用代码实现一下：

/**
 * 手写一个归并排序-
 * 归并排序遵循 归并模式
 * 分解：将n个元素的数组分解为2个 n/2个元素的数组
 * 解决：分别对2个子数组排序
 * 合并：合并2个已经排序的子数组
 *
 * @param array
 */
public static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid, right);
    }
}

/**
 * 将两个数组 合并 [min, mid] [mid+1, max]
 *
 * @param array
 * @param left
 * @param mid
 * @param right
 */
public static void merge(int[] array, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;

    while (i <= mid && j <= right) {
        if (array[i] <= array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = array[i++];
    }

    while (j <= right) {
        temp[k++] = array[j++];
    }

    for (int p = 0; p < temp.length; p++) {
        array[left + p] = temp[p];
    }

}

public static void main(String[] args) {
    int[] array = new int[]{9, 8, 6, 7, 5, 1, 3, 4, 2, 0};
    System.out.println("排序前数组" + Arrays.toString(array));
    mergeSort(array, 0, array.length - 1);
    System.out.println("排序后数组" + Arrays.toString(array));
}

递归式

当一个算法包含对其自身的递归调用时，我们往往可以用递归方程或递归式来描述其运行时间，该方程根据在较小上的运行时间来描述在规模为n的问题上的总运行时间。

最大子数组问题

给一个数组，找出一个具有最大和的连续子数组，返回最大和。

leetcode 53. Maximum Subarray

/**
 * 思路
 * 分解：将数组分为2个 子数组
 * 解决：两个子数组的 最大和 可以直接求得， 包含中间点 的 最大和 经过特殊计算一下
 * 合并：返回两个子数组 最大和 中 最大的一个 或者 返回 包含中间点 的最大和
 *
 * @param nums
 * @return
 */
public static int maxSubArray(int[] nums) {
    return calcMaxSubarray(nums, 0, (nums.length - 1) / 2, nums.length - 1);
}

/**
 * 计算最大子数组
 *
 * @param array
 * @param left
 * @param mid
 * @param right
 * @return
 */
public static int calcMaxSubarray(int[] array, int left, int mid, int right) {
    // left >= right 跳出递归
    if (left >= right) {
        return array[left];
    }

    // 左面子数组 最大值
    int leftMax = calcMaxSubarray(array, left, (left + mid) / 2, mid);
    // 右面子数组 最大值
    int rightMax = calcMaxSubarray(array, mid + 1, (mid + 1 + right) / 2, right);
    // 包含中间点的 两个子数组 的最大值 初始值 设为 中点的值
    int midMax = array[mid], temp = midMax;

    for (int i = mid - 1; i >= left; i--) {
        temp += array[i];
        midMax = Math.max(temp, midMax);
    }

    temp = midMax;

    for (int i = mid + 1; i <= right; i++) {
        temp += array[i];
        midMax = Math.max(temp, midMax);
    }

    return Math.max(midMax, Math.max(leftMax, rightMax));
}