嗨客网搜索
寻找两个正序数组的中位数

描述

leetcode 官方第 4 题。给定两个大小为 m 和 n 的正序(从小到大)数组 nums1nums2。请你找出并返回这两个正序数组的中位数。

示例1:

输入:nums1 = [1,3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1,2,3] ,中位数 2

示例2:

输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5

示例3:

输入:nums1 = [0,0], nums2 = [0,0] 输出:0.00000

示例4:

输入:nums1 = [], nums2 = [1] 输出:1.00000

示例5:

输入:nums1 = [2], nums2 = [] 输出:2.00000

提示:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

思路

这边我们可以考虑将两个数组合并,然后求合并后的数组的中位数。因为它的合并前的两个数据都是有序排序的。

下面是两个数组的和长度是奇数:

11_寻找两个正序数组的中位数.png

因为数组 1 和 数组 2 是有序的数组,所以我们新定义一个数组,将两个数组内容按照顺序存放在该数组里面,然后取出中位数。因为是奇位数,所以就取中间的数 3/2 = 1。即返回 2。因为数组是从 0 索引开始。

下面我们再以一个长度是偶数的例子:

12_寻找两个正序数组的中位数.png

我们可以看到,合并后的数组是偶数长度,它的长度是 4。4/2 = 2。所以我们需要取 2-1 这个索引的数和 2 这个索引的数。然后相加除以 2.0。如果不除以 2.0 系统会默认认为是整数类型。

代码具体实现

Java语言版本

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { //数组1的长度 int nums1Length = nums1.length; //数组2的长度 int nums2Length = nums2.length; //最终数组的总长度 int returnNumsLength = nums1Length + nums2Length; //定义一个最终数组 int[] retNums = new int[returnNumsLength]; //遍历到的数据1的索引初始值 int nums1Index = 0; //遍历的索引2的索引初始值 int nums2Index = 0; //表示 num1 是否遍历完 boolean nums1EndFlag = false; //表示 num2 是否遍历完 boolean nums2EndFlag = false; for(int i=0;i<returnNumsLength ;i++){ int tmpNum1 = 0; if(nums1Index <= nums1Length -1){ tmpNum1 = nums1[nums1Index]; }else{ //表示已经数组1已经被遍历结束 nums1EndFlag = true; } int tmpNum2 = 0; if(nums2Index <= nums2Length-1){ tmpNum2 = nums2[nums2Index]; }else{ //表示数组2已经遍历结束 nums2EndFlag = true; } //如果数组1被遍历结束了,将数组2的数据获取直接赋值 if(nums1EndFlag){ retNums[i] = tmpNum2; nums2Index ++; continue; } //如果数组2被遍历结束了,将数组1的数据直接赋值给返回数组 if(nums2EndFlag){ retNums[i] = tmpNum1; nums1Index ++; continue; } if(tmpNum1 >= tmpNum2){ retNums[i] = tmpNum2; nums2Index ++; }else{ retNums[i] = tmpNum1; nums1Index ++; } } //特殊情况,数组长度为1 if(returnNumsLength == 1){ return retNums[0]; } if(returnNumsLength % 2 == 0){ int num1 = retNums[returnNumsLength/2]; int num2 = retNums[returnNumsLength/2 - 1 ]; return (num1 + num2)/2.0; }else{ return retNums[returnNumsLength / 2]; } } }

Go语言版本

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { //数组1的长度 nums1Length := len(nums1) //数组2的长度 nums2Length := len(nums2) //最终数组的总长度 returnNumsLength := (nums1Length + nums2Length) //定义一个最终数组 retNums := make([]int, returnNumsLength) //遍历到的数据1的索引初始值 nums1Index := 0 //遍历的索引2的索引初始值 nums2Index := 0 //表示 num1 是否遍历完 nums1EndFlag := false //表示 num2 是否遍历完 nums2EndFlag := false for i := 0;i<returnNumsLength;i++{ tmpNum1 := 0 if nums1Index <= nums1Length -1{ tmpNum1 = nums1[nums1Index] }else{ //表示已经数组1已经被遍历结束 nums1EndFlag = true } tmpNum2 := 0 if nums2Index <= nums2Length-1{ tmpNum2 = nums2[nums2Index] }else{ //表示数组2已经遍历结束 nums2EndFlag = true } //如果数组1被遍历结束了,将数组2的数据获取直接赋值 if nums1EndFlag{ retNums[i] = tmpNum2 nums2Index ++ continue } //如果数组2被遍历结束了,将数组1的数据直接赋值给返回数组 if nums2EndFlag { retNums[i] = tmpNum1 nums1Index ++ continue } if tmpNum1 >= tmpNum2 { retNums[i] = tmpNum2 nums2Index ++ }else{ retNums[i] = tmpNum1 nums1Index ++ } } //特殊情况,数组长度为1 if returnNumsLength == 1{ return float64(retNums[0]) } if returnNumsLength % 2 == 0 { num1 := retNums[returnNumsLength/2] num2 := retNums[returnNumsLength/2 - 1 ] return (float64(num1) + float64(num2))/2.0; }else{ return float64(retNums[returnNumsLength / 2]) } }
嗨客网顶部