（每日一练c++）CC147 两个有序数组的中位数

迈不过友情╰ 2023-10-04 17:57 20阅读 0赞

### 描述 ###

有两个大小分别为m和n的有序数组A和B。请找出这两个数组的中位数。你需要给出时间复杂度在O(log (m+n))以内的算法。

### 示例1 ###

输入：

[],[1]

复制返回值：

1.00000

//合并数组，然后快速确定中间值
    /*解题思路：
    （1）第一步将两个有序数组合并成一个有序的数组（或者向量）（类似于两个有序链表的合并）
    （2）得到最终的数组（或者向量）长度为m+n，然后判断是有奇数个值，还是有偶数个值
    （3）如果有奇数个值，那么只有一个中间值，对应的编号为 （数组（或者向量）长度 -1）/2，取出值，直接返回
    （4）如果有偶数个值，那么有两个中间值，对应编号为：
        1）数组（或者向量）长度 /2 2）数组（或者向量）长度 /2 - 1
    （5）取出对应的值，然后求平均，得到最终结果 */
    class Solution {
    public:
        double findMedianSortedArrays(int A[], int m, int B[], int n) {
            int C[m+n];
            memset(C,0,(m+n)*sizeof(int));
            int k=0;
            int i=0,j=0;//定义下标，其中i是向量1的下标，j是向量2的下标
            while(i<m&&j<n)
            {
                
                if(A[i]<=B[j])
                    C[k++]=A[i++];
                else
                    C[k++]=B[j++];
    
            }
             //数组B还有剩余部分，将数组B剩余部分依次插入
            if(i==m)
            {
                while(j<n)
                    C[k++]=B[j++];
            }    
            else if(j==n)//数组A还有剩余部分，将数组A剩余部分依次插入
            {
                while(i<m)
                    C[k++]=A[i++];
            }
            if((m+n)&1)//有奇数个值（一个中间值）
                return C[(m+n)>>1]*1.0;
            else有偶数个值（两个中间值，求平均值）
            	return (C[(m+n)>>1]+C[((m+n)>>1)-1])*0.5;   -号优先级比>>高
        }
    };