题目描述：

  1. 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
  2. 示例 1：
  4. 输入：nums1 = [1,3], nums2 = [2]
  5. 输出：2.00000
  6. 解释：合并数组 = [1,2,3] ，中位数 2
  7. 示例 2：
  9. 输入：nums1 = [1,2], nums2 = [3,4]
  10. 输出：2.50000
  11. 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
  12. 示例 3：
  14. 输入：nums1 = [0,0], nums2 = [0,0]
  15. 输出：0.00000
  16. 示例 4：
  18. 输入：nums1 = [], nums2 = [1]
  19. 输出：1.00000
  20. 示例 5：
  22. 输入：nums1 = [2], nums2 = []
  23. 输出：2.00000
  25. 提示：
  26. nums1.length == m
  27. nums2.length == n
  28. 0 <= m <= 1000
  29. 0 <= n <= 1000
  30. 1 <= m + n <= 2000
  31. -106 <= nums1[i], nums2[i] <= 106
  32. 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

解题思路：

把两个数组合并，然后进行排序，取出中位数

代码实现：

自己实现了快速排序。

  1. /*
  2.  * @lc app=leetcode.cn id=4 lang=golang
  3.  *
  4.  * [4] 寻找两个正序数组的中位数
  5.  */
  7. // @lc code=start
  8. func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
  9.     nums1 = append(nums1, nums2...)
  10.     quickSort(nums1)
  11.     mid := len(nums1) / 2
  12.     if len(nums1)%2 == 1 { //有可能合并的数组中的元素个数为单数
  13.         return float64(nums1[mid])
  14.     }
  15.     return (float64(nums1[mid-1]) + float64(nums1[mid])) / 2.0
  16. }
  18. func quickSort(s []int) {
  19.     if len(s) <= 1 {
  20.         return
  21.     }
  22.     reference := s[0]
  23.     left, right := 0, len(s)-1
  24.     i := 1
  25.     for left < right {
  26.         if s[i] < reference {
  27.             s[left], s[i] = s[i], s[left]
  28.             left++
  29.             i++
  30.         } else {
  31.             s[right], s[i] = s[i], s[right]
  32.             right--
  33.         }
  34.     }
  35.     quickSort(s[:left])
  36.     quickSort(s[left+1:])
  37. }
  39. // @lc code=end

LeetCode