专栏首页蛮三刀的后端开发专栏[Leetcode][python]Median of Two Sorted Arrays/两个排序数组的中位数

[Leetcode][python]Median of Two Sorted Arrays/两个排序数组的中位数

题目大意

求两个已经排好序的数列的中位数

解题思路

下面两个方法也适用于查找第k大的数

方法一

https://www.cnblogs.com/TenosDoIt/p/3554479.html

复杂度为O(k)的算法,在归并两个数组的过程中,如果如果已经选择的元素达到k(或中位数),就不需要再归并下去了。

方法二

转自:http://www.cnblogs.com/zuoyuan/p/3759682.html

首先我们来看如何找到两个数列的第k小个数,即程序中getKth(A, B , k)函数的实现。

用一个例子来说明这个问题:

A = {1,3,5,7} B = {2,4,6,8,9,10};

如果要求第7个小的数,A数列的元素个数为4,B数列的元素个数为6;

k/2 = 7/2 = 3,而A中的第3个数A[2]=5;B中的第3个数B[2]=6;

A[2]小于B[2];则A[0],A[1],A[2]中必然不可能有第7个小的数。

因为A[2]小于B[2],所以比A[2]小的数最多可能为A[0], A[1], B[0], B[1]这四个数,也就是说A[2]最多可能是第5个大的数,由于我们要求的是getKth(A, B, 7);现在就变成了求getKth(A’, B, 4);

即A’ = {7},因为A[0],A[1],A[2]中没有解,所以我们直接删掉它们就可以了。

B不变,求这两个数列的第4个小的数,这个可以使用递归来实现。

代码

class Solution(object):

    def getKth(self, A, B, k):
        lenA = len(A)
        lenB = len(B)
        if lenA > lenB:  # 保证A比B短
            return self.getKth(B, A, k)
        if lenA == 0:  # A已为空,直接返回B中间数
            return B[k - 1]
        if k == 1:   # 如果找的是第一个,直接返回两个数组比较小的那个
            return min(A[0], B[0])

        pa = min(k/2, lenA)
        print 'pa:', pa, 'pb', k-pa
        pb = k - pa

        print 'A[pa - 1]', A[pa - 1], 'B[pb - 1]',B[pb - 1]
        # 索引为pa和pb,所以是A[pa - 1] 和 B[pb - 1]
        if A[pa - 1] <= B[pb - 1]:
            return self.getKth(A[pa:], B, pb)
        else:
            return self.getKth(A, B[pb:], pa)

    def findMedianSortedArrays(self, A, B):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        lenA = len(A)
        lenB = len(B)
        if (lenA + lenB) % 2 == 1: 
            return self.getKth(A, B, (lenA + lenB)/2 + 1)
        else:
            return  (self.getKth(A, B, (lenA + lenB)/2) + self.getKth(A, B, (lenA + lenB)/2 + 1)) * 0.5

总结

分治法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [Leetcode][python]Longest Substring Without Repeating Characters/无重复字符的最长子串

    给定一个字符串,从中找出不含重复字符的最长子串的长度。 例如,”abcabcbb”的不含重复字母的最长子串为”abc”,其长度是3。”bbbbb”的最长子串...

    后端技术漫谈
  • [Leetcode][python]Binary Tree Level Order Traversal

    参考:链接 将树每一层的节点存在一个列表中,遍历列表中的元素,如果该节点有左右节点的话,就把它们加入一个临时列表,这样当遍历结束时,下一层的节点也按照顺序存...

    后端技术漫谈
  • [Leetcode][python]Reverse Nodes in k-Group/k个一组翻转链表

    参考: https://shenjie1993.gitbooks.io/leetcode-python/025%20Reverse%20Nodes%20in...

    后端技术漫谈
  • 直播、短视频只是互联网家装玩家的集体自嗨

    在直播电商风靡的背后,人们对于流量的追求有增无减。一时间,直播在不同领域里都开始出现。互联网家装领域无可幸免,同样加入到了对于直播的拥抱行列当中,越来越多的人开...

    孟永辉
  • 聊聊canal-go的SimpleCanalConnector

    canal-go-v1.0.7/client/simple_canal_connector.go

    codecraft
  • 聊聊canal-go的SimpleCanalConnector

    canal-go-v1.0.7/client/simple_canal_connector.go

    codecraft
  • HTML被恶意注入JS弹广告

    继续查看http://45.126.123.80:118/t.php 一堆代码,获取各种信息。。。

    Light413
  • 福利来一枚:虚拟云服务器

    逆天博客所作的服务器还有1天就过期了,发挥点余热,送个没有部署过的同志练练手(本来准备还有7天的时候放出来的,忘记。。。) ? 说来惭愧,博客开了一年了,没怎么...

    逸鹏
  • PostgreSQL与Oracle对应的函数

    1.What is PostgreSQL equivalent of SYSDATE from Oracle?

    shirayner
  • 树状数组模块(个人模板)

    owent

扫码关注云+社区

领取腾讯云代金券