Day 28: Divide and Conquer

这是什麽

分而治之，分治法！

分治法的步骤是：

1. 将一个问题拆解成多个可以处理的小问题後
2. 处理、击破每个小问题後
3. 收集每个小问题的答案，组合出最後的答案。

有趣的地方在於，如果问题拆解前、拆解後可以套用同一方法处理，其实就是递回法（Recursion）

刷题：4. Median of Two Sorted Arrays

连结

题目

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Follow up: The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

思考

这题很明显可以用 Merge Sort 处理，或是一个一个比较也可以。特别要注意是中位数的选取：

• 合并後的阵列长度为偶数，中位数是中间两个数相加除2。
• 合并後的阵列长度为基数，中位数选取中间即可。

解题

JS

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
const findMedianSortedArrays = (nums1, nums2) => {
  let i = 0;
  let j = 0;
  let k = 0;
  const nums1Length = nums1.length;
  const nums2Length = nums2.length;
  const resultLength = nums1Length + nums2Length;
  let result = new Array(resultLength);

  while (k < resultLength) {
    if (i >= nums1Length) {
      result[k] = nums2[j];
      j++;
    } else if (j >= nums2Length) {
      result[k] = nums1[i];
      i++;
    } else if (nums1[i] > nums2[j]) {
      result[k] = nums2[j];
      j++;
    } else {
      result[k] = nums1[i];
      i++;
    }

    k++;
  }

  let indexOfMedian = resultLength >> 1;

  if ((resultLength % 2) !== 0) {
    return result[indexOfMedian];
  }

  return (result[indexOfMedian - 1] + result[indexOfMedian]) / 2;
};

Java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int i = 0;
        int j = 0;
        int k = 0;
        int nums1Length = nums1.length;
        int nums2Length = nums2.length;
        int resultLength = nums1Length + nums2Length;
        int[] result = new int[resultLength];

        while (k < resultLength) {
            if (i >= nums1Length) {
                result[k] = nums2[j];
                j++;
            } else if (j >= nums2Length) {
                result[k] = nums1[i];
                i++;
            } else if (nums1[i] > nums2[j]) {
                result[k] = nums2[j];
                j++;
            } else {
                result[k] = nums1[i];
                i++;
            }

            k++;
        }

        int indexOfMedian = resultLength >> 1;

        if ((resultLength % 2) != 0) {
            return (double)result[indexOfMedian];
        }

        return (double)(result[indexOfMedian - 1] + result[indexOfMedian]) / 2;
    }
}

C

double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size)
{
    int i = 0;
    int j = 0;
    int k = 0;
    int resultLength = nums1Size + nums2Size;
    int *result = calloc(resultLength, sizeof(int *));

    while (k < resultLength)
    {
        if (i >= nums1Size)
        {
            result[k] = nums2[j];
            j++;
        }
        else if (j >= nums2Size)
        {
            result[k] = nums1[i];
            i++;
        }
        else if (nums1[i] > nums2[j])
        {
            result[k] = nums2[j];
            j++;
        }
        else
        {
            result[k] = nums1[i];
            i++;
        }

        k++;
    }

    int indexOfMedian = resultLength >> 1;

    if ((resultLength % 2) != 0)
    {
        return (double)result[indexOfMedian];
    }

    return (double)(result[indexOfMedian - 1] + result[indexOfMedian]) / 2;
}

看法

这题本身已经拆的够小，用不着进一步拆解，只需要组合阵列、求得中位数即可。
有趣的地方在於，C 可以找到使用递回的方法处理，效果更快！程序码的世界就是这般多采多姿。

结论

分治法除了刷题时会使用到，也可以套用在处理资料时，如何有效地建构所需变数结构。
与其说分治法是演算法，倒不如说是一种逻辑思维的运用。