0004.Median of Two Sorted Arrays
题目大意
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
解题思路
-
给出两个有序数组，要求找出这两个数组合并以后的有序数组中的中位数。要求时间复杂度为 O(log (m+n))。
-
这一题最容易想到的办法是把两个数组合并，然后取出中位数。但是合并有序数组的操作是
O(m+n)的，不符合题意。看到题目给的log的时间复杂度，很容易联想到二分搜索。 -
由于要找到最终合并以后数组的中位数，两个数组的总大小也知道，所以中间这个位置也是知道的。只需要二分搜索一个数组中切分的位置，另一个数组中切分的位置也能得到。为了使得时间复杂度最小，所以二分搜索两个数组中长度较小的那个数组。
-
关键的问题是如何切分数组 1 和数组 2 。其实就是如何切分数组 1 。先随便二分产生一个
midA，切分的线何时算满足了中位数的条件呢？即，线左边的数都小于右边的数，即，nums1[midA-1] ≤ nums2[midB] && nums2[midB-1] ≤ nums1[midA]。如果这些条件都不满足，切分线就需要调整。如果nums1[midA] < nums2[midB-1]，说明midA这条线划分出来左边的数小了，切分线应该右移；如果nums1[midA-1] > nums2[midB]，说明 midA 这条线划分出来左边的数大了，切分线应该左移。经过多次调整以后，切分线总能找到满足条件的解。 -
假设现在找到了切分的两条线了，
数组 1在切分线两边的下标分别是midA - 1和midA。数组 2在切分线两边的下标分别是midB - 1和midB。最终合并成最终数组，如果数组长度是奇数，那么中位数就是max(nums1[midA-1], nums2[midB-1])。如果数组长度是偶数，那么中间位置的两个数依次是：max(nums1[midA-1], nums2[midB-1])和min(nums1[midA], nums2[midB])，那么中位数就是(max(nums1[midA-1], nums2[midB-1]) + min(nums1[midA], nums2[midB])) / 2。图示见下图：
image.png
代码
func max(a int,b int)int{
if a >= b{
return a
}else if b > a{
return b
}
return 0
}
func min(a int,b int)int{
if a <= b{
return a
}else if b < a{
return b
}
return 0
}
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
// 假设 nums1 的长度小
if len(nums1) > len(nums2) {
return findMedianSortedArrays(nums2,nums1) // 交换nums1和nums2
}
low := 0
high :=len(nums1)
k := (len(nums1)+len(nums2)+1)>>1 // 两个数组合并的分界线
nums1Mid := 0
nums2Mid := 0
// 确定num1的分界线
for low <= high {
// 求第一个数组的分界线，分界限右侧是 mid，分界线左侧是 mid - 1
nums1Mid = low + (high-low) >>1
// 求第二个数组的分界线，用两个数组的分界线减去第一个数组的分界线
nums2Mid = k - nums1Mid
// nums1 中的分界线划多了，要向左边移动
if nums1Mid > 0 && nums1[nums1Mid -1] > nums2[nums2Mid]{
high = nums1Mid - 1
// nums1 中的分界线划少了，要向右边移动
}else if nums1Mid != len(nums1) && nums1[nums1Mid] < nums2[nums2Mid -1]{
low = nums1Mid + 1
} else {
// 找到合适的划分了，需要输出最终结果了
// 分为奇数偶数 2 种情况
break
}
}
midLeft, midRight := 0, 0
// 确定合并数组的左边
if nums1Mid == 0{
midLeft = nums2[nums2Mid - 1]
}else if nums2Mid == 0{
midLeft = nums1[nums1Mid - 1]
}else{
midLeft = max(nums1[nums1Mid - 1],nums2[nums2Mid - 1])
}
// 根据奇偶来处理合并数组,&1(奇数等于1，偶数等于0)
if (len(nums1)+len(nums2))&1 == 1{
return float64(midLeft) // 奇数返回
}
// 偶数
if nums1Mid == len(nums1) {
midRight = nums2[nums2Mid]
}else if nums2Mid == len(nums2){
midRight = nums1[nums1Mid]
}else{
midRight = min(nums1[nums1Mid],nums2[nums2Mid])
}
return float64(midLeft+midRight)/2
}
题外话：
把其中的if else if else 换成switch时候，运行超时
// 运行超时
// switch {
// case nums1Mid > 0 && nums1[nums1Mid -1] > nums2[nums2Mid]:
// high = nums1Mid - 1
// case nums1Mid != len(nums1) && nums1[nums1Mid] < nums2[nums2Mid -1]:
// low = nums1Mid + 1
// default:
// break
// }
思路：
1、预备工作，先把整型比较大小的函数写好
2、把长度小归为第一个数组，然后初始化第一个数组的首尾指针
3、初始化三个中间分界线，两个数组中间分界线为0，合并数组的分界线（两数组长度和+1之后除2）
4、第一个数组分界线有两个指针确定，第二数组的分界线由合拍数组的和减去第一数组的分界线确定
5、保证nums1[midA-1] ≤ nums2[midB] && nums2[midB-1] ≤ nums1[midA]
6、确定合并数组的左边，有一边等于0，就确定另一边，不为0，求两个的最大的
7、根据奇偶来处理合并数组,&1(奇数等于1，偶数等于0)
8、确定合并数组额右边，有一边等于自身的最右边，就确定另一边，否则，求两个的最小值
9、返回左边和右边的和
