# LeetCode题解 15题 第二篇

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

```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```

## 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第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 八进