寻找两个正序数组的中位数-题解

题目描述

这是leetcode伤的第4题

题目解析

首先仔细看一下这个题目我们不难发现，其中最重要的一点就是两个数组为正序，由此我们不难想出一下两个解题思路：

第一个解题思路就是先将两个数组合并排序，然后再进行取中位数，但是有个问题是，如果我们只是用普通的排序来做这道题的话，题目中给的正序就是无效条件了，并且性能肯定也会大大下降。在经典的几大排序中，有一个排序的特点就与这个有序数组合并有关，那就是归并排序，所以我们这里最优是用的排序算法就是归并排序。
第二个题解思路，因为两个数组是有序的并且他们的长度也是已经知道的，所以我们也可以不使用排序，我们可以维护两个指针通过这个指针去找到中位数

归并解法

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    nums := append(nums1,nums2...)
    Sort(nums)
    lens := len(nums)
    var res float64
    if lens % 2 ==0{
        res = (float64(nums[lens/2-1])+float64(nums[lens/2]))/2
        return res
    }else{
        return float64(nums[lens/2])
    }
    
}
func Sort(arr []int) {
	var tamp = make([]int, len(arr))
	copy(tamp, arr)
	sort(arr, 0, len(arr)-1, tamp)
}
func sort(arr []int, l int, r int, tamp []int) {
	if l >= r {
		return
	}
	mid := l + (r-l)/2
	sort(arr, l, mid, tamp)
	sort(arr, mid+1, r, tamp)
	//加上如下判断
	//优化：当数组本身为有序时，这里的时间复杂度将会变成O(n)
	if arr[mid] > arr[mid+1] {
		merge(arr, l, mid, r, tamp)
	}
}


//合并两个有序的区间arr[l,mid],arr[mid+1,r]
func merge(arr []int, l int, mid int, r int, tamp []int) {
	copy(tamp[l:r+1], arr[l:r+1])
	i := l
	j := mid + 1
	//每轮循环为arr[k]赋值
	for k := l; k <= r; k++ {
		if i > mid {
			arr[k] = tamp[j]
			j++
		} else if j > r {
			arr[k] = tamp[i]
			i++
		} else if tamp[i] < tamp[j] {
			arr[k] = tamp[i]
			i++
		} else {
			arr[k] = tamp[j]
			j++
		}
		//arr[i]和arr[j]
	}
}