练习：分治算法--有序数组寻找中位数

题： 给定两个长度为m 和 n 有序组数array1 和array2，请找出这个有序数组的中位数。
'''
eg.
[1,3]和[5,6]，中位数是4
[1,2,5,8,9]和[2,3,4,5],中位数是4
'''

### 直接方法，使用内置排序函数sort
# 时间复杂度最高：O((n+m)log(n+m))，空间复杂度：O(n+m)

 1 class Solution(object):
 2     def findmedian(self,nums1,nums2):
 3         nums3=nums1+nums2
 4         nums3.sort()
 5         return (nums3[len(nums3)//2]+nums3[(len(nums3)-1)//2])/2
 6 # eg.
 7 nums1=[1,2,5,8,9]
 8 nums2=[2,3,4,5]
 9 demo=Solution()
10 re=demo.findmedian(nums1,nums2)
11 print(re) # 4.0 再取个整

### 利用双指针将两个数组排序
# 时间复杂度最高：O(n+m)，空间复杂度：O(n+m)

 1 class Solution2(object):
 2     def findmedian(self,nums1,nums2):
 3         nums3=[]
 4         j=i=0
 5         # 利用双指针将两个数组排序
 6         while(i<len(nums1) and j<len(nums2)):
 7             if nums1[i]<nums2[j]:
 8                 nums3.append(nums1[i])
 9                 i+=1
10             else:
11                 nums3.append(nums2[j])
12                 j+=1
13         if i==len(nums1) and j!=len(nums2):
14             for x in nums2[j:]:
15                 nums3.append(nums2[x])
16         if j==len(nums2) and i!=len(nums1):
17             for x in nums1[i:]:
18                 nums3.append(nums1[x])
19         # 返回len(nums3)/2 和(len(nums3)-1)/2 向下取整的均值
20         return (nums3[len(nums3) // 2] + nums3[(len(nums3) - 1) // 2]) / 2

### 采用二分法，再分治处理
# 时间复杂度最高：O(log(min(n+m)))，空间复杂度：O(1)

 1 class Solution3:
 2     # 定义一个取数组中位数的函数
 3     def getmediannum(self,nums):
 4         return (nums[len(nums) // 2] + nums[(len(nums) - 1) // 2]) / 2
 5 
 6     def findmedian(self,array1,array2):
 7         len1=len(array1)
 8         len2=len(array2)
 9         # array1为短数组，array2为短数组，不符合则换
10         if len1>len2:
11             return self.findmedian(array2,array1)
12 
13         if len1<=2: # 较短的数组长度小于等于2
14             if len2>4:  # 较长的数组长度大于4,
15                 p1=math.ceil(len2/2)-2  # math.ceil()向上取整
16                 array2=array2[p1:-p1]   # 取数组中间部分
17             # 合并两部分再排序
18             nums=array1+array2
19             nums.sort()
20             # 可以直接对剩余部分寻找中位数
21             return self.getmediannum(nums)
22 
23         p2=math.ceil(len1/2)-1
24         # 较短的数组长度大于2
25         # 当较短的数组的中位数较小时，array1 中位数之前的所有元素就被截去，array2 尾部截去相同的长度，再递归两数组
26         if self.getmediannum(array1)<self.getmediannum(array2):
27             return self.findmedian(array1[p2:],array2[:-p2])
28         else:
29             return self.findmedian(array1[:-p2],array2[p2:])
30 # eg.
31 nums1=[1,2,5,8,9]
32 nums2=[2,3,4,5]
33 demo3=Solution3()
34 re=demo3.findmedian(nums1,nums2)
35 print(re) # 4.0 再取个整

2023-9-10笔记