LeetCode：寻找两个正序数组的中位数

当前位置:

首页 > temp > python入门教程 >

LeetCode：寻找两个正序数组的中位数

题目：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

原题链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

	`解法一：代码简洁，但用了内置排序函数。`
	`def findMedianSortedArrays(nums1, nums2):`
	`# 判空`
	`if not nums1 and not nums2:`
	`return 0`
	`# 一方为空`
	`elif (not nums1 and nums2) or (not nums2 and nums1):`
	`nums = nums1 or nums2`
	`# 非空`
	`else:`
	`nums = nums1 + nums2`
	`nums.sort()`
	`if len(nums) % 2 != 0:`
	`mid = int((len(nums) - 1) / 2)`
	`return nums[mid]`
	`else:`
	`right = int((len(nums) / 2))`
	`left = int(right - 1)`
	`return (nums[left] + nums[right]) / 2`

	`解法二：真正面试中，考官往往不许我们使用任何内置排序函数，所以只能自己手写排序！`
	`以下的排序不是通用排序方法，而是根据题目--正序（从小到大）数组写的一个排序，仅供参考。`
	`def findMedianSortedArrays(nums1, nums2):`
	`# 判空`
	`if not nums1 and not nums2:`
	`return 0`
	`# 一方为空`
	`elif (not nums1 and nums2) or (not nums2 and nums1):`
	`new_nums = nums1 or nums2`
	`# 非空`
	`else:`
	`# 不使用内置排序函数，自己手写排序`
	`import copy`
	`len1, len2 = len(nums1), len(nums2)`
	`longer_nums = nums1 if len1 > len2 else nums2`
	`short_nums = nums2 if len1 > len2 else nums1`
	`# 此处要进行深拷贝，否则后面 new_nums 插入元素时，longer_nums 也会同步变化`
	`new_nums = copy.deepcopy(nums1) if len1 > len2 else copy.deepcopy(nums2)`
	`count = 0`
	`for idx, num in enumerate(longer_nums):`
	`while count < len(short_nums):`
	`if short_nums[count] > num:`
	`if idx == len(longer_nums) - 1:`
	`new_nums.extend(short_nums[count:])`
	`break`
	`else:`
	`# idx + count ：第二个往后的元素在插入时，除了idx下标位，还因为前面元素的插入额外移动了count位`
	`new_nums.insert(idx + count, short_nums[count])`
	`count += 1`
	`if idx == len(longer_nums) - 1:`
	`break`
	`if len(new_nums) % 2 != 0:`
	`mid = int((len(new_nums) - 1) / 2)`
	`return new_nums[mid]`
	`else:`
	`right = int((len(new_nums) / 2))`
	`left = int(right - 1)`
	`return (new_nums[left] + new_nums[right]) / 2`

栏目列表