chatgpt两个有序数组的中值

chatgpt两个有序数组的中值.md

在C++中，可以使用二分查找的思想来找到两个有序数组的中值。具体步骤如下：

1. 确保数组nums1是较短的数组，如果不是，则交换nums1和nums2。
2. 定义两个变量，m和n，分别表示数组nums1和nums2的长度。
3. 定义两个指针，left和right，分别指向数组nums1和nums2的划分位置。
4. 初始化left为0，right为m。
5. 进行二分查找，直到找到合适的划分位置。
   • 令i = (left + right) / 2，j = (m + n + 1) / 2 - i。
   • 如果nums1[i - 1] > nums2[j]，则说明划分位置过大，需要将right左移。
   • 如果nums2[j - 1] > nums1[i]，则说明划分位置过小，需要将left右移。
   • 否则，划分位置合适，停止二分查找。
6. 根据划分位置，计算中值。
   • 如果m + n为奇数，中值为max(nums1[i - 1], nums2[j - 1])。
   • 如果m + n为偶数，中值为(max(nums1[i - 1], nums2[j - 1]) + min(nums1[i], nums2[j])) / 2.0。

下面是使用C++实现的代码：

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    // 确保nums1是较短的数组
    if (nums1.size() > nums2.size()) {
        nums1.swap(nums2);
    }
    
    int m = nums1.size();
    int n = nums2.size();
    int left = 0;
    int right = m;
    
    while (left <= right) {
        int i = (left + right) / 2;
        int j = (m + n + 1) / 2 - i;
        
        if (i < m && nums2[j - 1] > nums1[i]) {
            left = i + 1;
        } else if (i > 0 && nums1[i - 1] > nums2[j]) {
            right = i - 1;
        } else {
            int maxLeft;
            if (i == 0) {
                maxLeft = nums2[j - 1];
            } else if (j == 0) {
                maxLeft = nums1[i - 1];
            } else {
                maxLeft = max(nums1[i - 1], nums2[j - 1]);
            }
            
            if ((m + n) % 2 == 1) {
                return maxLeft;
            }
            
            int minRight;
            if (i == m) {
                minRight = nums2[j];
            } else if (j == n) {
                minRight = nums1[i];
            } else {
                minRight = min(nums1[i], nums2[j]);
            }
            
            return (maxLeft + minRight) / 2.0;
        }
    }
    
    return 0.0;
}

使用示例：

vector<int> nums1 = {1, 3};
vector<int> nums2 = {2};
cout << findMedianSortedArrays(nums1, nums2) << endl;  // 输出 2.0

vector<int> nums3 = {1, 2};
vector<int> nums4 = {3, 4};
cout << findMedianSortedArrays(nums3, nums4) << endl;  // 输出 2.5

希望对你有帮助！