這是什麼

分而治之，分治法！

分治法的步驟是：

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 可以找到使用遞迴的方法處理，效果更快！程式碼的世界就是這般多采多姿。

結論

分治法除了刷題時會使用到，也可以套用在處理資料時，如何有效地建構所需變數結構。
與其說分治法是演算法，倒不如說是一種邏輯思維的運用。