赞
赏
leetcode 官方第 4 题。给定两个大小为 m 和 n 的正序(从小到大)数组 nums1
和 nums2
。请你找出并返回这两个正序数组的中位数。
示例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
提示:
这边我们可以考虑将两个数组合并,然后求合并后的数组的中位数。因为它的合并前的两个数据都是有序排序的。
下面是两个数组的和长度是奇数:
因为数组 1 和 数组 2 是有序的数组,所以我们新定义一个数组,将两个数组内容按照顺序存放在该数组里面,然后取出中位数。因为是奇位数,所以就取中间的数 3/2 = 1。即返回 2。因为数组是从 0 索引开始。
下面我们再以一个长度是偶数的例子:
我们可以看到,合并后的数组是偶数长度,它的长度是 4。4/2 = 2。所以我们需要取 2-1 这个索引的数和 2 这个索引的数。然后相加除以 2.0。如果不除以 2.0 系统会默认认为是整数类型。
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];
}
}
}
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])
}
}