【leetcode练习题】4. 寻找两个有序数组的中位数

文章目录一瞥

感悟收获题目算法解析官方实现代码自己实现的代码1：小技巧：正负无穷表示的方法：Python类中的self到底是干啥的下面说说typing模块常用的方式：Python列表解析配合if else

感悟收获

思路对于编程序来说是特别重要的，先要思考清楚所处理的问题，相处一个算法结构再去实现问题！快速实现问题的能力是需要具有的；；对于这些题目而言，算法往往比实现这些问题更加重要；非常震撼的算法思想，令人有些惊叹！！！python 除法要除以2.0，不然是整除

题目

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

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

你可以假设 nums1 和 nums2 不会同时为空。

算法解析

官方实现代码

from typing import List class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m = len(nums1) n = len(nums2) size_left_total = (m + n + 1) >> 1 # 数组是奇数时,中位数就是中位数,size左 = size右 + 1(包括进去中位数) size右最小索引 为i # 数组为偶数时,中位数分左右中位数,size左 = size右 size 右最小索引为i left = 0 right = m # find i and j while left < right: i = (left + right) >> 1 # 得到的是中位数的索引,或者是右中位数的索引 j = size_left_total - i #print('i,j:', i, j) if nums2[j - 1] > nums1[i]: # nums2 的左边最大的数比 num1 右边最小的数要大,说明边界线i需要右移 # left 需要变大,i在[left ,right ]里面选择 left = i + 1 # i+1 如果进入死循环,则选i+1 否则 i else: right= i #i 或者 i -1 # i and j have been found i = right j = size_left_total - i nums1_left_max = float('-inf') if i == 0 else nums1[i - 1] nums1_right_min = float('inf') if i == m else nums1[i] nums2_left_max = float('-inf') if j == 0 else nums2[j - 1] nums2_right_min = float('inf') if j == n else nums2[j] if (m + n) & 1: # 数组总和数量为奇数 return max(nums1_left_max, nums2_left_max) else: return float((max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2)

这里上面应该除以2.0，不然会有错误

自己实现的代码1：

nums1=[4,5,6,9,10] nums2=[1,2] temp=0; i=0; j=0; length=(len(nums1)+len(nums2))/2 while (i+j < length): if (len(nums1)==0): if (len(nums2)% 2==0): print(nums2[len(nums2)//2-1]) temp=(nums2[len(nums2)//2-1]+nums2[len(nums2)//2])/2 else:temp=nums2[len(nums2)//2] i=length elif (len(nums2)==0): if (len(nums1)%2==0):temp=(nums1[len(nums1)//2-1]+nums1[len(nums1)//2])/2 else:temp=nums1[len(nums1)//2] i=length else: while (nums1[i]<=nums2[j]) &( i+j+1<length) : i=i+1 while (len(num2)==j)&(nums1[i]>=nums2[j]) &( i+j+1<length) : i=i+1 while (nums1[i]>=nums2[j]) & ( i+j+1<length) : j=j+1 while (len(num1)==i)&(nums1[i]>=nums2[j]) &( i+j+1<length) : i=i+1 if i+j+1>length: temp=min(nums1[i],nums2[j]) break if i+j+1==length: temp=(nums1[i]+nums2[j])/2 break print(temp)

小技巧：正负无穷表示的方法：

float('inf') float('-inf')

Python类中的self到底是干啥的

Python编写类的时候，每个函数参数第一个参数都是self，一开始我不管它到底是干嘛的，只知道必须要写上。后来对Python渐渐熟悉了一点，再回头看self的概念，似乎有点弄明白了。

首先明确的是self只有在类的方法中才会有，独立的函数或方法是不必带有self的。self在定义类的方法时是必须有的，虽然在调用时不必传入相应的参数。

self名称不是必须的，在python中self不是关键词，你可以定义成a或b或其它名字都可以,但是约定成俗（为了和其他编程语言统一，减少理解难度），不要搞另类，大家会不明白的。

下例中将self改为myname一样没有错误：

class Person: def _init_(myname,name): myname.name=name def sayhello(myname): print 'My name is:',myname.name p=Person('Bill') print p

self指的是类实例对象本身(注意：不是类本身)。

class Person: def _init_(self,name): self.name=name def sayhello(self): print 'My name is:',self.name p=Person('Bill') print p

在上述例子中，self指向Person的实例p。 为什么不是指向类本身呢，如下例子：

class Person: def _init_(self,name): self.name=name def sayhello(self): print 'My name is:',self.name p1=Person('Bill') p2 = Person('Apple') print p1

如果self指向类本身，那么当有多个实例对象时，self指向哪一个呢？

总结

self在定义时需要定义，但是在调用时会自动传入。

self的名字并不是规定死的，但是最好还是按照约定是用self

self总是指调用时的类的实例。

越努力越幸运。

下面说说typing模块常用的方式：

from typing import List, Tuple, Dict def add(a:int, string:str, f:float, b:bool) -> Tuple[List, Tuple, Dict, bool]: list1 = list(range(a)) tup = (string, string, string) d = {"a":f} bl = b return list1, tup, d,bl print(add(5,"hhhh", 2.3, False))

结果：([0, 1, 2, 3, 4], (‘hhhh’, ‘hhhh’, ‘hhhh’), {‘a’: 2.3}, False) 说明：

在传入参数时通过“参数名:类型”的形式声明参数的类型； 返回结果通过"-> 结果类型"的形式声明结果的类型。 在调用的时候如果参数的类型不正确pycharm会有提醒，但不会影响程序的运行。 对于如list列表等，还可以规定得更加具体一些，如：“-> List[str]”,规定返回的是列表，并且元素是字符串。 由于python天生支持多态，迭代器中的元素可能多种，如下：

from typing import List def func(a:int, string:str) -> List[int or str]: list1 = [] list1.append(a) list1.append(string) return list1

使用or关键字表示多种类型 typing常用的类型：

int,long,float: 整型,长整形,浮点型; bool,str: 布尔型，字符串类型； List, Tuple, Dict, Set:列表，元组，字典, 集合; Iterable,Iterator:可迭代类型，迭代器类型； Generator：生成器类型；

Python列表解析配合if else

2017-05-30 11:36:54 KeeJee 阅读数 15788更多 分类专栏： Python Python 用习惯列表解析之后会觉得超级酷，所以在尝试使用列表解析，把循环什么的写在一行里面。使用if的时候什么时候必须要有else，什么时候可以没有else一直没搞明白，直到今天！待我缓缓道来：

列表解析总共有两种形式：

[i for i in range(k) if condition]：此时if起条件判断作用，满足条件的，将被返回成为最终生成的列表的一员。

[i if condition else exp for exp]：此时if…else被用来赋值，满足条件的i以及else被用来生成最终的列表。

以上情况对多个for仍然成立。

print([i for i in range(10) if i%2 == 0]) print([i if i == 0 else 100 for i in range(10)]) [0, 2, 4, 6, 8] [0, 100, 100, 100, 100, 100, 100, 100, 100, 100]