LeetCode第4题：Python解法可行但C++陷入死循环的问题求助

问题根源 #

你的Python代码能正常运行，但C代码在输入nums1 = [1,3]、nums2 = [2]时陷入无限循环，核心原因是**Python与C的整数除法行为差异**：

• Python的//是向下取整（例如(0 + -1) // 2 = -1）
• C++的/是截断向零（例如(0 + -1) / 2 = 0）

当二分过程中r变为-1后，C++计算出的i始终为0，无法进入正确的分支，导致循环无法终止。

修复方案 #

修改i的计算逻辑，使其在C++中实现和Python一致的向下取整，同时用long long避免数组长度过大时的整数溢出：

修复后的完整代码 #

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> A = nums1;
        vector<int> B = nums2;
        int total = A.size() + B.size();
        int half = total / 2;
        
        // 确保A是较短的数组，优化二分效率
        if (B.size() < A.size()) {
            A.swap(B);
        }
        
        int l = 0;
        int r = A.size() - 1;
        while (true) {
            // 用long long计算避免溢出，实现向下取整
            long long ll_l = l;
            long long ll_r = r;
            int i = static_cast<int>((ll_l + ll_r) / 2);
            // 或者用条件判断实现向下取整（适用于int范围）
            // int i = (l + r) >= 0 ? (l + r) / 2 : ((l + r) - 1) / 2;
            
            int j = half - i - 2;
            
            int Aleft = (i >= 0) ? A[i] : INT_MIN;
            int Aright = ((i + 1) < A.size()) ? A[i + 1] : INT_MAX;
            int Bleft = (j >= 0) ? B[j] : INT_MIN;
            int Bright = ((j + 1) < B.size()) ? B[j + 1] : INT_MAX;
            
            if (Aleft <= Bright && Bleft <= Aright) {
                if (total % 2) {
                    return min(static_cast<double>(Aright), static_cast<double>(Bright));
                } else {
                    return (max(static_cast<double>(Aleft), static_cast<double>(Bleft)) + min(static_cast<double>(Aright), static_cast<double>(Bright))) / 2.0;
                }
            } else if (Aleft > Bright) {
                r = i - 1;
            } else {
                l = i + 1;
            }
        }
    }
};

int main() {
    Solution s;
    vector<int> nums1 = {1, 3};
    vector<int> nums2 = {2};
    cout << s.findMedianSortedArrays(nums1, nums2) << endl;
    return 0;
}

关键修改点 #

1. 统一整数除法逻辑：
   使用long long类型计算l + r，再转换为int，确保在负数情况下实现向下取整（例如(0 + -1)作为long long计算时，-1 / 2 = -1）。
   也可以用条件判断实现向下取整（注释中的代码），适合不需要考虑大数溢出的场景。

2. 类型转换避免溢出：
   在计算max和min时，将int转换为double，避免两个INT_MAX相加导致的整数溢出（虽然当前案例不会触发，但这是通用的健壮性优化）。

测试验证 #

修复后输入nums1 = [1,3]、nums2 = [2]时：

1. 交换后A = [2]，B = [1,3]，total=3，half=1
2. 第一次循环：i=0，j=-1，判断Aleft(2) > Bright(1)，设置r=-1
3. 第二次循环：计算i=(0 + -1)/2 = -1，j=1 - (-1) -2=0
4. 此时Aleft=INT_MIN，Aright=2，Bleft=1，Bright=3，满足Aleft <= Bright且Bleft <= Aright
5. 因total是奇数，返回min(2,3)=2，循环正常终止

内容的提问来源于stack exchange，提问作者Joy Karmoker