首页 > 程序开发 > 软件开发 > 其他 > 正文
LeetCode算法部分
2017-03-20 09:29:32       个评论      
收藏    我要投稿

LeetCode算法部分:此题实际就是归并的问题,所以首先想到的是STL里的merge()。

double findMedianSortedArrays(vector& nums1, vector& nums2) {
        vector v(nums1.size()+nums2.size());
        merge(nums1.begin(),nums1.end(),nums2.begin(),nums2.end(),v.begin());
        double i;
        if(v.size()%2==0){
             i = (v[v.size()/2-1]+v[v.size()/2])/2.0;
        } else {
             i = v[(v.size()+1)/2-1];
        }
        return i;
    }

显然其时间复杂度要符合O(log(m+n))的要求,然而还有其它方法,下面就列举一种二分查找的方法,以更加清晰的体现分治的思想。

    int getkth(int s[], int m, int l[], int n, int k){
        // let m <= n
        if (m > n) 
            return getkth(l, n, s, m, k);
        if (m == 0)
            return l[k - 1];
        if (k == 1)
            return min(s[0], l[0]);

        int i = min(m, k / 2), j = min(n, k / 2);
        if (s[i - 1] > l[j - 1])
            return getkth(s, m, l + j, n - j, k - j);
        else
            return getkth(s + i, m - i, l, n, k - i);
        return 0;
    }

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int l = (m + n + 1) >> 1;
        int r = (m + n + 2) >> 1;
        return (getkth(A, m ,B, n, l) + getkth(A, m, B, n, r)) / 2.0;
    }
点击复制链接 与好友分享!回本站首页
上一篇:IO流之文件
下一篇:Java实现图片验证码
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站