分治法 — Divide and Conquer 三階段與 Master Theorem | 資料結構與演算法

// 標準歸併排序（in-place 版本）
function mergeSortInPlace(arr: number[], left = 0, right = arr.length - 1): void {
  if (left >= right) return;  // base case：單一元素不需排序

  const mid = Math.floor((left + right) / 2);
  mergeSortInPlace(arr, left, mid);       // Conquer 左半
  mergeSortInPlace(arr, mid + 1, right);  // Conquer 右半
  mergeRange(arr, left, mid, right);      // Combine
}

function mergeRange(arr: number[], left: number, mid: number, right: number): void {
  // 暫存左右兩段的拷貝（避免覆蓋）
  const leftPart = arr.slice(left, mid + 1);
  const rightPart = arr.slice(mid + 1, right + 1);

  let i = 0, j = 0, k = left;
  while (i < leftPart.length && j < rightPart.length) {
    // <= 保持穩定性：相等時優先取左側
    if (leftPart[i] <= rightPart[j]) {
      arr[k++] = leftPart[i++];
    } else {
      arr[k++] = rightPart[j++];
    }
  }
  // 將剩餘元素填入
  while (i < leftPart.length) arr[k++] = leftPart[i++];
  while (j < rightPart.length) arr[k++] = rightPart[j++];
}

// 在 Merge Sort 中順便計算逆序對數量
function mergeSortAndCount(arr: number[], left = 0, right = arr.length - 1): number {
  if (left >= right) return 0;

  const mid = Math.floor((left + right) / 2);
  let count = 0;
  count += mergeSortAndCount(arr, left, mid);
  count += mergeSortAndCount(arr, mid + 1, right);
  count += mergeAndCount(arr, left, mid, right);
  return count;
}

function mergeAndCount(arr: number[], left: number, mid: number, right: number): number {
  const leftPart = arr.slice(left, mid + 1);
  const rightPart = arr.slice(mid + 1, right + 1);

  let i = 0, j = 0, k = left;
  let inversions = 0;

  while (i < leftPart.length && j < rightPart.length) {
    if (leftPart[i] <= rightPart[j]) {
      arr[k++] = leftPart[i++];
    } else {
      // rightPart[j] 小於 leftPart[i..end] 中的所有元素
      // 形成 (leftPart.length - i) 個逆序對
      inversions += leftPart.length - i;
      arr[k++] = rightPart[j++];
    }
  }
  while (i < leftPart.length) arr[k++] = leftPart[i++];
  while (j < rightPart.length) arr[k++] = rightPart[j++];

  return inversions;
}

// 測試
const arr1 = [8, 3, 5, 1, 9, 2, 7, 4];
mergeSortInPlace(arr1);
console.log(arr1);  // 輸出：[1, 2, 3, 4, 5, 7, 8, 9]

const arr2 = [5, 2, 3, 1];
console.log(mergeSortAndCount([...arr2]));  // 輸出：6（逆序對：(5,2),(5,3),(5,1),(2,1),(3,1),(3,1) 共 6 對）

// 隨機化 Quick Select，期望 O(n) 時間，O(1) 額外空間
function findKthLargest(nums: number[], k: number): number {
  // 找第 k 大 = 升序陣列中 index = n-k 的元素（0-indexed）
  return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

function quickSelect(arr: number[], left: number, right: number, targetIdx: number): number {
  if (left === right) return arr[left];

  // 隨機化 pivot：避免已排序輸入的 O(n²) 退化
  const pivotIdx = left + Math.floor(Math.random() * (right - left + 1));
  const partitionIdx = lomutoPartition(arr, left, right, pivotIdx);

  if (partitionIdx === targetIdx) {
    return arr[partitionIdx];          // pivot 就是目標！
  } else if (partitionIdx < targetIdx) {
    return quickSelect(arr, partitionIdx + 1, right, targetIdx);   // 目標在右半
  } else {
    return quickSelect(arr, left, partitionIdx - 1, targetIdx);    // 目標在左半
  }
}

function lomutoPartition(arr: number[], left: number, right: number, pivotIdx: number): number {
  const pivot = arr[pivotIdx];
  // 將 pivot 移到末尾暫存
  [arr[pivotIdx], arr[right]] = [arr[right], arr[pivotIdx]];

  let storeIdx = left;
  for (let i = left; i < right; i++) {
    if (arr[i] < pivot) {
      [arr[storeIdx], arr[i]] = [arr[i], arr[storeIdx]];
      storeIdx++;
    }
  }
  // 將 pivot 放回正確位置
  [arr[storeIdx], arr[right]] = [arr[right], arr[storeIdx]];
  return storeIdx;
}

// 測試
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));         // 輸出：5（第 2 大）
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 輸出：4（第 4 大）

interface Point {
  x: number;
  y: number;
}

function distance(p1: Point, p2: Point): number {
  return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
}

function closestPair(points: Point[]): number {
  // 預先按 X 排序，後續遞迴只需按 Y 排序
  const sortedByX = [...points].sort((a, b) => a.x - b.x);
  return closestPairRec(sortedByX);
}

function closestPairRec(pts: Point[]): number {
  const n = pts.length;

  if (n <= 3) {
    // base case：暴力求解小規模問題
    let minDist = Infinity;
    for (let i = 0; i < n; i++) {
      for (let j = i + 1; j < n; j++) {
        minDist = Math.min(minDist, distance(pts[i], pts[j]));
      }
    }
    return minDist;
  }

  const mid = Math.floor(n / 2);
  const midPoint = pts[mid];

  // Divide + Conquer：分別求左右半的最近距離
  const leftMin = closestPairRec(pts.slice(0, mid));
  const rightMin = closestPairRec(pts.slice(mid));
  let d = Math.min(leftMin, rightMin);

  // Combine：找跨越中線的最近點對
  // 只需考慮距中線 d 以內的點（strip 區域）
  const strip = pts.filter(p => Math.abs(p.x - midPoint.x) < d);
  // 按 Y 排序後，只需比較 Y 差距 < d 的相鄰點（至多 7 個）
  strip.sort((a, b) => a.y - b.y);

  for (let i = 0; i < strip.length; i++) {
    // 數學上可以證明最多只需比較後面 7 個點
    for (let j = i + 1; j < strip.length && strip[j].y - strip[i].y < d; j++) {
      d = Math.min(d, distance(strip[i], strip[j]));
    }
  }

  return d;
}

// 測試
const points: Point[] = [
  { x: 2, y: 3 }, { x: 12, y: 30 }, { x: 40, y: 50 },
  { x: 5, y: 1 }, { x: 12, y: 10 }, { x: 3, y: 4 }
];
console.log(closestPair(points).toFixed(3));  // 輸出：1.414（點(2,3)和(3,4)）

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (lists.length === 0) return null;
  if (lists.length === 1) return lists[0];

  // 分治：對半拆分，遞迴合併
  function divideAndMerge(left: number, right: number): ListNode | null {
    if (left > right) return null;
    if (left === right) return lists[left];

    const mid = Math.floor((left + right) / 2);
    return merge2(divideAndMerge(left, mid), divideAndMerge(mid + 1, right));
  }

  // 合併兩條有序鏈結串列
  function merge2(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1.val <= l2.val) {
      l1.next = merge2(l1.next, l2);
      return l1;
    }
    l2.next = merge2(l1, l2.next);
    return l2;
  }

  return divideAndMerge(0, lists.length - 1);
}

// 複雜度分析：
// k 條鏈結串列，總節點數 N
// 分治深度：log(k) 層
// 每層總合併工作：O(N)
// 總時間：O(N log k)，優於逐一合併的 O(Nk)

// 分治法求最大子陣列和
// 時間 O(n log n)，劣於 Kadane's O(n)，但展示分治精髓
function maxSubArrayDivide(nums: number[]): number {
  function solve(left: number, right: number): number {
    if (left === right) return nums[left];  // base case：單一元素

    const mid = Math.floor((left + right) / 2);

    // 子問題：左半與右半的最大子陣列和
    const leftMax = solve(left, mid);
    const rightMax = solve(mid + 1, right);

    // Combine：找跨越中點的最大子陣列和（必須包含 nums[mid] 和 nums[mid+1]）
    let leftCross = -Infinity, sum = 0;
    for (let i = mid; i >= left; i--) {
      sum += nums[i];
      leftCross = Math.max(leftCross, sum);
    }

    let rightCross = -Infinity;
    sum = 0;
    for (let i = mid + 1; i <= right; i++) {
      sum += nums[i];
      rightCross = Math.max(rightCross, sum);
    }

    const crossMax = leftCross + rightCross;

    // 三者取最大：左半、右半、跨中點
    return Math.max(leftMax, rightMax, crossMax);
  }

  return solve(0, nums.length - 1);
}

// 測試
console.log(maxSubArrayDivide([-2, 1, -3, 4, -1, 2, 1, -5, 4]));  // 輸出：6（子陣列 [4,-1,2,1]）
console.log(maxSubArrayDivide([1]));   // 輸出：1
console.log(maxSubArrayDivide([5, 4, -1, 7, 8]));  // 輸出：23

#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iostream>

// ━━━━━━━━━━ Merge Sort + 逆序對計數 ━━━━━━━━━━

class MergeSort {
public:
    long long inversions = 0;

    void sort(std::vector<int>& arr, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

private:
    void merge(std::vector<int>& arr, int left, int mid, int right) {
        std::vector<int> temp(right - left + 1);
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                // arr[i..mid] 都比 arr[j] 大，形成 (mid - i + 1) 個逆序對
                inversions += (mid - i + 1);
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        std::copy(temp.begin(), temp.end(), arr.begin() + left);
    }
};

// ━━━━━━━━━━ Quick Select（第 K 大元素）━━━━━━━━━━

class QuickSelectSolver {
public:
    // 手工實作：隨機化 Quick Select
    int findKthLargest(std::vector<int>& nums, int k) {
        int targetIdx = nums.size() - k;  // 第 k 大 = 第(n-k)小（0-indexed）
        return select(nums, 0, nums.size() - 1, targetIdx);
    }

    // STL nth_element（底層使用 Introselect，保證 O(n) 最壞情況）
    int findKthLargestSTL(std::vector<int> nums, int k) {
        int targetIdx = nums.size() - k;
        std::nth_element(nums.begin(), nums.begin() + targetIdx, nums.end());
        return nums[targetIdx];
    }

private:
    int select(std::vector<int>& arr, int left, int right, int targetIdx) {
        if (left == right) return arr[left];

        int pivotIdx = left + rand() % (right - left + 1);  // 隨機化 pivot
        pivotIdx = partition(arr, left, right, pivotIdx);

        if (pivotIdx == targetIdx) return arr[pivotIdx];
        else if (pivotIdx < targetIdx) return select(arr, pivotIdx + 1, right, targetIdx);
        else return select(arr, left, pivotIdx - 1, targetIdx);
    }

    int partition(std::vector<int>& arr, int left, int right, int pivotIdx) {
        int pivot = arr[pivotIdx];
        std::swap(arr[pivotIdx], arr[right]);
        int storeIdx = left;

        for (int i = left; i < right; i++) {
            if (arr[i] < pivot) {
                std::swap(arr[storeIdx++], arr[i]);
            }
        }
        std::swap(arr[storeIdx], arr[right]);
        return storeIdx;
    }
};

// ━━━━━━━━━━ Merge K Sorted Lists（分治）━━━━━━━━━━

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class MergeKListsSolver {
public:
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        return mergeRange(lists, 0, lists.size() - 1);
    }

private:
    ListNode* mergeRange(std::vector<ListNode*>& lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        auto l = mergeRange(lists, left, mid);
        auto r = mergeRange(lists, mid + 1, right);
        return merge2(l, r);
    }

    ListNode* merge2(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* cur = &dummy;

        while (l1 && l2) {
            if (l1->val <= l2->val) { cur->next = l1; l1 = l1->next; }
            else                    { cur->next = l2; l2 = l2->next; }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

// ━━━━━━━━━━ LeetCode 493 — Reverse Pairs ━━━━━━━━━━
// 計算所有 i < j 且 nums[i] > 2 * nums[j] 的配對數

class Solution493 {
    int total = 0;

    void mergeSort(std::vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // Step 1：計數（兩指標，O(n)，必須在合併前執行）
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && (long long)nums[i] > 2LL * nums[j]) j++;
            total += j - (mid + 1);
        }

        // Step 2：合併（獨立步驟，不能與計數混用）
        std::inplace_merge(nums.begin() + left,
                           nums.begin() + mid + 1,
                           nums.begin() + right + 1);
    }

public:
    int reversePairs(std::vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return total;
    }
};

// 並行 Merge Sort（利用 Promise.all 同時處理兩側）
class ParallelMergeSort {
  private readonly threshold: number;

  constructor(threshold: number = 1000) {
    this.threshold = threshold;  // 小於此規模時切回串行
  }

  async sort(arr: number[]): Promise<number[]> {
    if (arr.length <= this.threshold) {
      // 小問題直接串行排序（避免並行開銷超過收益）
      return [...arr].sort((a, b) => a - b);
    }

    const mid = Math.floor(arr.length / 2);

    // 並行處理左右兩側（實際場景可使用 Web Workers）
    const [left, right] = await Promise.all([
      this.sort(arr.slice(0, mid)),
      this.sort(arr.slice(mid))
    ]);

    return this.merge(left, right);  // 串行合併（合併本身難以並行化）
  }

  private merge(left: number[], right: number[]): number[] {
    const result: number[] = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length) {
      result.push(left[i] <= right[j] ? left[i++] : right[j++]);
    }
    return result.concat(left.slice(i), right.slice(j));
  }
}

function majorityElement(nums: number[]): number {
  function solve(left: number, right: number): number {
    if (left === right) return nums[left];  // base case：只有一個元素

    const mid = Math.floor((left + right) / 2);
    const leftMajority = solve(left, mid);    // 左半的眾數
    const rightMajority = solve(mid + 1, right); // 右半的眾數

    if (leftMajority === rightMajority) return leftMajority;

    // 兩側眾數不同，計算各自在整個範圍內出現的次數
    let leftCount = 0, rightCount = 0;
    for (let i = left; i <= right; i++) {
      if (nums[i] === leftMajority) leftCount++;
      else if (nums[i] === rightMajority) rightCount++;
    }

    return leftCount > rightCount ? leftMajority : rightMajority;
  }

  return solve(0, nums.length - 1);
}

// 測試
console.log(majorityElement([3, 2, 3]));       // 輸出：3
console.log(majorityElement([2, 2, 1, 1, 1, 2, 2]));  // 輸出：2
// 注意：此分治解法時間 O(n log n)，優化版可用 Boyer-Moore 投票法達 O(n)

// 非標準分治，但體現分治「剪掉無關部分」的精神
function searchMatrix(matrix: number[][], target: number): boolean {
  // 從右上角開始，每次可以剪掉一整行或一整列
  let row = 0, col = matrix[0].length - 1;

  while (row < matrix.length && col >= 0) {
    if (matrix[row][col] === target) {
      return true;
    } else if (matrix[row][col] > target) {
      col--;  // 當前列所有元素都 >= target，剪掉整列
    } else {
      row++;  // 當前行所有元素都 <= target，剪掉整行
    }
  }
  return false;
}

// 測試
const matrix = [
  [1,  4,  7,  11, 15],
  [2,  5,  8,  12, 19],
  [3,  6,  9,  16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
];
console.log(searchMatrix(matrix, 5));   // 輸出：true
console.log(searchMatrix(matrix, 20));  // 輸出：false

// 錯誤：沒有處理 arr.length === 1 的情況
function badMergeSort(arr: number[]): number[] {
  // if (arr.length <= 1) return arr;  ← 忘記！空陣列仍會再次分割
  const mid = Math.floor(arr.length / 2);
  return merge(badMergeSort(arr.slice(0, mid)), badMergeSort(arr.slice(mid)));
}

// 正確：所有 arr.length <= 1 的情況直接回傳
function goodMergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;  // ← 必要的 base case
  const mid = Math.floor(arr.length / 2);
  return merge(goodMergeSort(arr.slice(0, mid)), goodMergeSort(arr.slice(mid)));
}

// 錯誤：計數和合併混在同一個 while 迴圈
// 合併過程改變陣列順序，導致計數不正確
function badReversePairs(arr: number[], left: number, mid: number, right: number): number {
  let count = 0, i = left, j = mid + 1;
  const temp: number[] = [];
  while (i <= mid && j <= right) {
    if (arr[i] > 2 * arr[j]) {
      count += (mid - i + 1); // arr[i] 被推進合併後，計數邏輯已錯
      temp.push(arr[j++]);
    } else {
      temp.push(arr[i++]);  // ← 計數與合併混用，結果錯誤
    }
  }
  return count;
}

// 正確：計數和合併必須分成兩個獨立步驟
function goodReversePairs(arr: number[], left: number, mid: number, right: number): number {
  // Step 1：計數（雙指標掃描，不修改陣列）
  let count = 0;
  let j = mid + 1;
  for (let i = left; i <= mid; i++) {
    while (j <= right && arr[i] > 2 * arr[j]) j++;
    count += j - (mid + 1);
  }
  // Step 2：標準合併（獨立執行）
  // ...（合併邏輯）
  return count;
}

// 錯誤：nums[j] 很大時 2 * nums[j] 溢位 int
if (nums[i] > 2 * nums[j]) { ... }  // ← 危險！

// 正確：轉型為 long long 再計算
if ((long long)nums[i] > 2LL * nums[j]) { ... }  // ← 安全