leetcode 4(python实现)

leetcode 4

题目描述

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)).

You may assume nums1 and nums2 cannot be both empty.

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目解析

• 思路一

看到这道题的第一反应就是用归并排序来做，将两个有序的数组首先合并为一个有序的数组，再返回这个有序数组的中位数，就是我们需要得到的结果。

但是，题目中还限制了一条，The overall run time complexity should be O(log (m+n)). 合并排序实现的代码提交时超出了时间限制，为什么会超出呢？我们先来分析一下我们的实现代码的时间复杂度

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:Key = []i = 0j = 0length1 = len(nums1)length2 = len(nums2)while (i < length1 and j < length2):if nums1[i] <= nums2[j]:Key.append(nums1[i])i = i + 1else:Key.append(nums2[j])j = j + 1while (i < length1):Key.append(nums1[i])i = i + 1while (j < length2):Key.append(nums2[j])length = len(Key)if length % 2 == 0:return (Key[length // 2] + Key[length // 2 - 1]) / 2else:return float(Key[length // 2])

输入的两个数组的长度分别为$m$和$n$，我们需要遍历两个数组，所以整体代码的时间复杂度为$O(m+n)$， 这显然不符合题目要求的时间复杂度

• 思路二

另一种思路，直接利用python的内置排序函数对nums1和nums2的整体进行排序，然后提取出中位数即可，这种方法倒是通过了，难道说内置的排序函数时间复杂度要低很多？但这种方法是有点偷巧了。

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:Key = sorted(nums1 + nums2)length = len(Key)if length % 2 == 0:return (Key[length // 2] + Key[length // 2 - 1]) / 2else:return float(Key[length // 2])

这种方法对于两个未排好序的数组求他们的中位数同样有效，而官方解答则无法处理这种情况，而且这种方法代码、思路要简洁得多.

• 思路三，利用二分的思想，使得时间复杂度达到$O(log(min(M,N)))$

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:if len(nums1) > len(nums2):nums1, nums2 = nums2, nums1m = len(nums1)n = len(nums2)left = 0right = mwhile left <= right:i = (left + right) >> 1j = ((m + n + 1) >> 1) - 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 nums1_left_max <= nums2_right_min and nums2_left_max <= nums1_right_min:if (m + n) & 1:return max(nums1_left_max, nums2_left_max)else:return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2elif nums2_left_max > nums1_right_min:left = i + 1else:right = i - 1        

其中涉及到两个小技巧， >>1 与 & 1

• $(left+right)>>1$ 相当于(left + right)除以2，即$(left+right)/2$，这种位运算的方式会快很多，而且可以避免整数溢出的问题（虽然python中不会发生溢出问题）。
  我们假设使用的是java语言，left、right为正数，当left和right过大时，超出了数值的表示范围，就会发生溢出，它们的和就会变成负数。
  但我们使用 >> 运算符，即使发生溢出，得到的结果依然是正确的结果。 详细原理之后另写一篇博文来叙述。
• $(m+n)\&1$ 相当于$(m+n)$对$2$取余，我们判断一个数是否可以被2整除，实际上就是判断该数的二进制表示的最后一位是0还是1，如果是1，则无法被2整除，如果是0，则可以被2整除。所以我们可以利用&运算符来判断最后一位是1还是0，从而判断该数是否能被2整除。（&为按位与运算符，只有均为真时返回真）

二分法这种思路可以参见这篇题解：

两个有序数组的中位数

讲的非常清晰！

算法的时间复杂度和空间复杂度

现实生活中有着各种各样的算法，我们如何来评判算法的优劣呢？一般是从时间和空间两个维度来考量一个算法的优劣

• 时间纬度：也就是执行算法需要消耗的时间，通常用时间复杂度来刻画
• 空间纬度： 执行算法需要消耗的内存空间，通常用空间复杂度来刻画

从时间的角度去考量一个算法，我们很容易就能想到可以利用执行算法消耗的实际时间来刻画，但是这种方式会受到硬件、软件的影响，同一个算法，使用性能不同的计算机来执行，消耗的时间自然不同，所以科学家们以另一种角度来刻画算法的时间消耗，即算法的渐进复杂度，它不是算法的实际运行时间，而是用来刻画代码执行时间随输入变化的增长趋势。

我们用大O符号表示法来描述时间复杂度，其公式为$T(n)=O(f(n)),其中f(n)为算法每行代码的执行次数之和$。

常见的算法复杂度有下面几种：

• 常数阶$O(1)$，算法的执行时间不随输入的变化而变化
• 对数阶$O(logN)$，算法的执行时间随输入的变化呈对数曲线变化
• 线性阶$O(N)$
• 线性对数阶$O(N\ast logN)$
• 平方阶 O ( n 2 ) O(n^2) O(n2)
• k次方阶 O ( n k ) O(n^k) O(nk)
• 指数阶 O ( 2 N ) O(2^N) O(2N)

这里我们仅举一个对数阶的例子，其他的例子都很容易想到

while i < N:i = 2 * i

第二行的执行次数为x，有 2 x = N 2^x=N 2x=N，得到$x=logN$，即执行次数为$logN$，即算法的执行时间与输入量呈对数关系

同样，空间复杂度也是刻画随输入的变化程序实际占用空间的变化趋势，而不是指实际占用的空间大小。

常见的空间复杂度有，$O(1),O(n)$等

int[] x = new int[N]

该段代码的空间复杂度即为$O(N)$

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！