LeetCode题解 15题 第二篇

之前写过一篇,这是第二篇。上一篇用了多种编程语言来做,这一次是以学算法为主,所以打算都用python来完成。

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

这道题比较难,参考了这篇文章http://blog.csdn.net/yutianzuijin/article/details/11499917/,然后用python写了程序

其中第k小数算法是关键。总结下思路,争取以后我也可以多发明些这类nb的算法。

主要是将求A得问题巧妙地转换为求B的问题,并且在逻辑上证明是合理的。

class Solution(object):

    def findKth(self, arr1, len1, arr2, len2, k):
        #always assume that len1 is equal or smaller than len2
        if len1 > len2:
            return self.findKth(arr2, len2, arr1, len1, k)
        if len1 == 0:
            return arr2[k - 1]
        if k == 1:
            return min(arr1[0], arr2[0])
        #divide k into two parts
        pa = min(k / 2, len1)
        pb = k - pa
        if arr1[pa - 1] < arr2[pb - 1]:
            return self.findKth(arr1[pa:], len1 - pa, arr2, len2, k - pa)
        elif arr1[pa - 1] > arr2[pb - 1]:
            return self.findKth(arr1, len1, arr2[pb:], len2 - pb, k - pb)
        else:
            return arr1[pa - 1]  

    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums1_len = len(nums1)
        nums2_len = len(nums2)
        total = nums1_len + nums2_len
        if total & 1:
            return self.findKth(nums1, nums1_len, nums2, nums2_len, total/2 + 1)
        else:
            ret1 = self.findKth(nums1, nums1_len, nums2, nums2_len, total/2)
            ret2 = self.findKth(nums1, nums1_len, nums2,nums2_len, total/2 + 1)
            return float((ret1  + ret2)) / 2
				



				
时间: 01-15

LeetCode题解 15题 第二篇的相关文章

LeetCode第15题 三数之和

/* 给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组. 注意:答案中不可以包含重复的三元组. 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]*/ /* 思路: 首先想到的肯定是穷举,时间复杂度为O(n^3) , 但如果使用这种方法,也实在称不上算法题了,果不其然,超时. [

leetcode:1-5题代码整理

以下是这段时间抽时间刷的前5题,都是自己想的解法,或许不是最优解,只是整理下,方便日后优化提升 1. Two Sum: class Solution: # @return a tuple, (index1, index2) def twoSum(self, num, target): dict = {} for i in xrange(len(num)): if dict.get(target-num[i], None) == None: dict[num[i]] = i else: retur

leetcode第15题--3Sum

Problem: Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

leetcode中第一题twosum问题解答算法的可行性证明

leetcode中第一题twosum问题解答算法的可行性证明 一.引入 关于leetcode中第一题twosum问题,网上已有不少高人做出过解答,并提出了切实可行的算法实现.我在解答该题时参考了博客http://www.zixue7.com/article-9576-1.html的解答.为让读者更直观地阅读和理解本文,先简要摘录以上博客的内容如下: 题目还原 Two Sum Given an array of integers, find two numbers such that they a

leetcode -day 15 Distinct Subsequences

1.  Distinct Subsequences Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters with

LeetCode 第 204 题 (Count Primes)

LeetCode 第 204 题 (Count Primes) Description: Count the number of prime numbers less than a non-negative number, n. 计算小于 N 的素数的个数.这道题目比较简单.但是想提高计算效率与需要费点脑筋. 判断一个数字 n 是不是素数的简单方法是 用 n 去除 2,3,4,-,n?1,如果都不能整除就说明这个数是素数. 按照这个思路可以写个简单的函数. bool isPrime(int n)

第二篇第十一章灭火救援设施

2019/1/4 [录播]2018一消精华班-实务-一级消防工程师-环球网校 http://v.edu24ol.com/?type=lesson&id=178944&gid=16157 1/7 1.第二篇第十一章灭火救援设施 第十一章 灭火救援设施 学习要求:了解消防车道.消防登高面.救援窗及直升机停机坪的设置目的,熟悉其设置的作用,掌握消防车道.消防登高 面.救援窗及直升机停机坪及消防电梯的设置范围.数量.要求. 第一节消防车道 街区内的道路应考虑消防车的通行,室外消火栓的保护半径在15

LeetCode开心刷题五十一天——118. Pascal&#39;s Triangle 接触跳转表概念,不知用处 lamda逗号导致表达式加法奇怪不理解119. Pascal&#39;s Triangle II

118. Pascal's Triangle Easy 87984FavoriteShare Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it. Example: Input: 5 Output: [ [1],

Python之路【第二篇】:Python基础(一)

Python之路[第二篇]:Python基础(一) 入门知识拾遗 一.作用域 对于变量的作用域,执行声明并在内存中存在,该变量就可以在下面的代码中使用. 1 2 3 if 1==1:     name = 'wupeiqi' print  name 下面的结论对吗? 外层变量,可以被内层变量使用 内层变量,无法被外层变量使用 二.三元运算 1 result = 值1 if 条件 else 值2 如果条件为真:result = 值1如果条件为假:result = 值2 三.进制 二进制,01 八进