algorithms►leetcode

025-寻找两个正序数组的中位数（二分查找）

寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

在不要求算法复杂度的情况下，个人认为先和并后排序的方法更简单易懂， 有手就行。

1
2
3
4
5
6
7
8
9
10
11
var findMedianSortedArrays = function(nums1, nums2) {
    const combined = nums1.concat(nums2);
    const sortedCombined = combined.sort((a, b) => a - b); // 修正：按数值排序
    
    const length = sortedCombined.length;
    if (length % 2 === 1) {
        return sortedCombined[Math.floor(length / 2)];
    } else {
        return (sortedCombined[(length / 2) - 1] + sortedCombined[length / 2]) / 2;
    }
};

下面是二分法的详细解析， O(log(min(m,n))

终极解答方案：二分查找法求两个有序数组的中位数

1. 核心思想

  • 二分查找短数组：在较短的数组上执行二分查找，确定分割点 partitionX。
  • 自动计算长数组分割点：partitionY = (m + n + 1) / 2 - partitionX。
  • 验证分割有效性：检查左半部分的最大值是否 ≤ 右半部分的最小值。

2. 完整代码

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
var findMedianSortedArrays = function(nums1, nums2) {
    // 确保 nums1 是较短的数组
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }
    const m = nums1.length, n = nums2.length;
    const k = Math.floor((m + n + 1) / 2); // 中位数位置
    
    // 初始化二分查找边界
    let low = 0, high = m;
    
    while (low <= high) {
        // 在 nums1 中尝试分割点 partitionX
        const partitionX = Math.floor((low + high) / 2);
        const partitionY = k - partitionX; // nums2 的分割点
        
        // 处理边界情况（分割点在数组两端）
        const maxLeftX = (partitionX === 0) ? -Infinity : nums1[partitionX - 1];
        const minRightX = (partitionX === m) ? Infinity : nums1[partitionX];
        const maxLeftY = (partitionY === 0) ? -Infinity : nums2[partitionY - 1];
        const minRightY = (partitionY === n) ? Infinity : nums2[partitionY];
        
        // 检查分割是否有效
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            // 计算中位数
            if ((m + n) % 2 === 1) {
                return Math.max(maxLeftX, maxLeftY); // 奇数长度
            } else {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2; // 偶数长度
            }
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1; // 左移分割点
        } else {
            low = partitionX + 1;  // 右移分割点
        }
    }
};

3. 分步图解（示例数组 [1,3,5,7] 和 [2,4,5,6]）

Step 1：初始化
  • nums1 = [1,3,5,7]（m=4），nums2 = [2,4,5,6]（n=4）
  • k = (4+4+1)/2 = 4（中位数位置）
  • low = 0，high = 4
Step 2：第一次迭代（partitionX=2）
nums1分割: [1,3 | 5,7]  (partitionX=2)
nums2分割: [2,4 | 5,6]  (partitionY=4-2=2)

关键值:
- maxLeftX = 3, minRightX = 5
- maxLeftY = 4, minRightY = 5

检查:
3 ≤ 5 (True) 且 4 ≤ 5 (True) → 分割有效！
Step 3：计算中位数
  • 总长度 m+n=8（偶数）：
    • 中位数 = (max(3,4) + min(5,5)) / 2 = (4 + 5) / 2 = 4.5

4. 关键步骤图示

nums1: [1, 3 | 5, 7]
          ↑ partitionX=2
nums2: [2, 4 | 5, 6]
          ↑ partitionY=2

合并后的虚拟数组:
左半部分: [1,3,2,4] → 最大=max(3,4)=4
右半部分: [5,7,5,6] → 最小=min(5,5)=5
中位数 = (4 + 5)/2 = 4.5

5. 复杂度分析

  • 时间复杂度：O(log(min(m,n)))
    仅在短数组上执行二分查找。
  • 空间复杂度：O(1)
    仅使用常数空间。

6. 边界情况处理

情况 处理方式 示例
分割点在 nums1 左端 maxLeftX = -Infinity partitionX=0
分割点在 nums1 右端 minRightX = Infinity partitionX=m
数组为空 直接返回另一数组的中位数 nums1=[], nums2=[1,2]

7. 为什么这样高效？

  • 短数组二分：减少搜索范围。
  • 数学约束：partitionX + partitionY = k 保证左右部分长度平衡。
  • 边界保护：-Infinity 和 Infinity 避免复杂条件判断。

总结

  1. 交换数组：确保 nums1 是较短的数组。
  2. 二分查找：在 nums1 上尝试分割点 partitionX。
  3. 验证分割：检查 maxLeft ≤ minRight。
  4. 调整方向：根据比较结果移动 low 或 high。
  5. 计算中位数：根据奇偶长度返回结果。
algorithms►leetcode

026-括号生成（DFS or DP）

括号生成

方法一：回溯法（DFS）

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
function generateParenthesis(n) {
    const result = [];
    
    function backtrack(current, open, close) {
        // 当字符串长度达到 2n 时，保存结果
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        
        // 只要左括号数量小于 n，就可以添加左括号
        if (open < n) {
            backtrack(current + '(', open + 1, close);
        }
        
        // 只有右括号数量小于左括号时，才能添加右括号（保证有效性）
        if (close < open) {
            backtrack(current + ')', open, close + 1);
        }
    }
    
    backtrack('', 0, 0);
    return result;
}

// 示例测试
console.log(generateParenthesis(3)); 
// 输出：["((()))", "(()())", "(())()", "()(())", "()()()"]
代码解析
  1. backtrack 函数：
    • current：当前构建的字符串。
    • open：已使用的左括号数量。
    • close：已使用的右括号数量。
  2. 终止条件：当 current.length === 2 * n 时，说明已生成一个有效组合，存入 result。
  3. 递归添加括号：
    • 如果左括号数量 < n，可以继续加 (。
    • 如果右括号数量 < 左括号数量，可以加 )（确保有效性）。

方法二：动态规划（DP）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function generateParenthesis(n) {
    const dp = Array.from({ length: n + 1 }, () => []);
    dp[0] = [""]; // 初始化：0 对括号是空字符串
    
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            // 组合所有可能的子问题解
            for (const left of dp[j]) {
                for (const right of dp[i - j - 1]) {
                    dp[i].push(`(${left})${right}`);
                }
            }
        }
    }
    
    return dp[n];
}

// 示例测试
console.log(generateParenthesis(3)); 
// 输出：["((()))", "(()())", "(())()", "()(())", "()()()"]
代码解析
  1. dp 数组：
    • dp[i] 存储 i 对括号的所有有效组合。
    • 初始化 dp[0] = [""]（0 对括号是空字符串）。
  2. **递推填充 dp**：
    • 对于 i 对括号，遍历 j 从 0 到 i-1：
      • dp[j] 的所有组合作为内部括号 left。
      • dp[i-j-1] 的所有组合作为外部括号 right。
      • 组合成 (${left})${right} 并存入 dp[i]。

两种方法对比

方法 时间复杂度 空间复杂度 适用场景
回溯法 O(4ⁿ/√n) O(n)（递归栈） 代码简洁，通用
动态规划 O(4ⁿ/√n) O(4ⁿ/√n) 可复用子问题解

如何选择？

  • 面试/快速实现：用 回溯法（逻辑清晰，代码短）。
  • 多次调用/优化：用 动态规划（避免重复计算）。

示例图解（n=2）

回溯法流程

1. 开始 -> '(' 
   -> '((' 
      -> '(()' 
         -> '(())' ✅
   -> '()'
      -> '()('
         -> '()()' ✅
结果：["(())", "()()"]

动态规划流程

dp[0]: [""]
dp[1]: ["()"]
dp[2]:
  - j=0: "(" + dp[0] + ")" + dp[1] → "()()"
  - j=1: "(" + dp[1] + ")" + dp[0] → "(())"
结果：["(())", "()()"]

总结

  • 回溯法：通过递归 + 剪枝生成所有有效组合。
  • 动态规划：利用子问题的解构建当前解（类似数学归纳法）。
  • JavaScript 注意点：递归时用 current + '(' 而非 +=（避免修改原字符串）。