LeetCode-4. 两个排序数组的中位数

淩亂°似流年 2022-05-26 11:30 181阅读 0赞

### 4. 两个排序数组的中位数 ###

[题目描述][Link 1]

--------------------

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

示例 1:

nums1 = [1, 3]
    nums2 = [2]
    
    中位数是 2.0

示例 2:

nums1 = [1, 2]
    nums2 = [3, 4]
    
    中位数是 (2 + 3)/2 = 2.5

*  [数组][Link 2] [二分查找][Link 3] [分治算法][Link 4]

--------------------

#include<bits/stdc++.h>
    using namespace std;
    /********************提交代码********************/
    double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
    {
        int *a=(int*)malloc((nums1Size+nums2Size+1)*sizeof(int));//将两个数组的值合并在一个数组中
        int *b=(int*)malloc((nums1Size+nums2Size+1)*sizeof(int));//排好序的合并数组
        int i,j=0,k,maxnum=0;
        double ans=0;
        for(i=0; i<nums1Size; ++i)
        {
            a[j++]=nums1[i];
            if(nums1[i]>maxnum)//记录最大值
                maxnum=nums1[i];
        }
        for(i=0; i<nums2Size; ++i)
        {
            a[j++]=nums2[i];
            if(nums2[i]>maxnum)
                maxnum=nums2[i];
        }
        int *cnt=(int*)malloc((maxnum+1)*sizeof(int));//哈希排序
        for(i=0; i<=maxnum; ++i)//初始化
            cnt[i]=0;
        for(i=0; i<nums1Size+nums2Size; ++i)
            ++cnt[a[i]];
        j=0;
        for(i=0; i<=maxnum; ++i)
            for(k=0; k<cnt[i]; ++k)//根据数出现的次数计入新的数组
            {
                b[j++]=i;
            }
        if((nums1Size+nums2Size)%2)//奇数个
            ans=b[(nums1Size+nums2Size)/2];
        else//偶数个
            ans=(b[(nums1Size+nums2Size)/2]+b[(nums1Size+nums2Size)/2-1])/2.0;
        return ans;
    }
    /***************************************************/
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int m,n;
        while(cin>>m>>n)
        {
            int a[1000],b[1000];
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            for(int i=0; i<m; ++i)
                cin>>a[i];
            for(int i=0; i<n; ++i)
                cin>>b[i];
            cout<<findMedianSortedArrays(a,m,b,n)<<endl;
        }
        return 0;
    }

感觉我的思路和题目的分类不太一致哇……

两个数组归到一个数组里放着，然后用哈希的思想排序。

忍不住吐槽，Σ(っ°Д°;)っ这居然是困难题？？？ 恕我直言，某些中等题都比这个让我头疼(•́へ•́╬)

因为是“要求算法的时间复杂度为 O(log (m+n))”？

就是只能扫一遍，用cnt数组记录每个数出现的次数，然后扫描cnt数组，值是几就表明这个数出现了几次，依次存起来就是有序数组辣(〃'▽'〃)

[Link 1]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/
[Link 2]: https://leetcode-cn.com/tag/array
[Link 3]: https://leetcode-cn.com/tag/binary-search
[Link 4]: https://leetcode-cn.com/tag/divide-and-conquer