关于leetcode:LeetCode4-寻找两个正序数组的中位数

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

进阶：你能设计一个工夫复杂度为 O(log (m+n)) 的算法解决此问题吗？

思路：

看到这道题的第一个思路是应用相似归并排序的形式，将两个数组合并成一个有序数组，在对这个有序数组求中位数。

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {nums := newNums(nums1, nums2)
    if len(nums)%2 == 1 {return float64(nums[len(nums)/2])
    } else {return float64(nums[len(nums)/2]+nums[len(nums)/2-1]) / 2.0
    }
}

func newNums(nums1, nums2 []int) []int {newnums := make([]int, len(nums1)+len(nums2))
    for i, j, k := 0, 0, 0; i < len(nums1) || j < len(nums2); k++ {
        // 如果有一个数组被读取完，则将另一个数组剩下的数字退出新创建数组的开端
        if i == len(nums1) {for ; j < len(nums2); j, k = j+1, k+1 {newnums[k] = nums2[j]
            }
            return newnums
        }
        if j == len(nums2) {for ; i < len(nums1); i, k = i+1, k+1 {newnums[k] = nums1[i]
            }
            return newnums
        }
        // 比拟两个数组将较小的退出新数组当中，并将指针的后移
        if nums1[i] < nums2[j] {newnums[k] = nums1[i]
            i++
        } else {newnums[k] = nums2[j]
            j++
        }
    }
    return newnums
}

然而应用这个办法合并数组至多须要 min(M,N) 次的比拟，所以算法的工夫复杂度为 O(m+n)，并不合乎题目的要求。

转化思路：

看到 O(log) 的复杂度，很容易就会想到二分查找，然而因为数据分布在两个数组这就为咱们的二分查找带来了艰难。咱们首先想到中位数实质是一个宰割，一侧的数都小于该数，另一侧则都大于该数，所以咱们能够从两边采取取总数一半的策略。具体步骤剖析如下：

package conf
// 分割线右边多一个数
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
   //1. 判断是奇数还是偶数，奇数返回分割线右边的第一个数，偶数返回分割线两侧的平均数
 var sum int
 sum = len(nums1) + len(nums2)
   if sum%2 == 1 {
      //2，在奇数内运行分割线的寻找函数
 return float64(getDivLine(nums1, nums2, sum/2+1))
   } else {
      //3，在偶数局部运行分割线的查找函数
 return float64(getDivLine(nums1, nums2, sum/2+1)+getDivLine(nums1, nums2, sum/2)) / 2.0
 }
}
func getDivLine(nums1, nums2 []int, need int) int {
   index1, index2 := 0, 0
 for {
      //1. 如果任意数组放入右边的量曾经等于数组大小，则返回另一数组已返回右边的大小，加需要数目。如果 need==1，则返回两数组分割线右边较小的数值。if index1 == len(nums1) {return nums2[index2+need-1]
      }
      if index2 == len(nums2) {return nums1[index1+need-1]
      }
      if need == 1 {return min(nums1[index1], nums2[index2])
      }
      //2. 将小于分割线所须要的数进行均分，失去对应两个数组所须要的小于分割线的数量
 half := need / 2
 //3. 别离比拟两数组须要的数和数组长度的比拟，如果长与数组长度，则返回数组的最初一个值
 newindex1 := min(index1+half, len(nums1)) - 1
 newindex2 := min(index2+half, len(nums2)) - 1
 pivot1, pivot2 := nums1[newindex1], nums2[newindex2]
      //4，比拟两个数组别离宰割后的大小，将较小的数组放入分割线的左侧，同时缩小需要数的数
 if pivot1 <= pivot2 {
         need -= newindex1 - index1 + 1
 index1 = newindex1 + 1
 } else {
         need -= newindex2 - index2 + 1
 index2 = newindex2 + 1
 }
   }
}
func min(x, y int) int {
   if x < y {return x}
   return y
}