数组-两个升序数组中位数

一、题目描述

二、解题思路

(一).基本思想：

如果列表总长度allsize( =arr1.size()+arr2.size() ) 为奇数时，中位数位置应该在两个列表排序后的第 allsize/2 位置处，如果allsize为偶数，中位数应该取 (allsize/2)-1 和 allsize/2 的平均数。

设置两个指针p1、p2，一个指向列表 arr1[0] ，一个指向列表 arr2[0] ，比较两个指针指向列表的值，值较小的指针往后移动一位

再次比较p1、p2，重复上述动作。

(二).注意：因为两个列表长度不一定相同，所以存在某一个指针p1遍历到列表末尾，但是仍然没有找到中位数，这时候中位数有可能就会出现①p1、p2均在列表中间，此时取二者较小值或者平均值、②在另一个列表中、③另一个列表中两个元素取平均值、④p1（此时在末尾）和p2取平均值、⑤p1（此时在末尾）这几种情况，下面就对各种可能出现的情况进行举例说明，以写出比较严谨的代码实现，覆盖各种可能出现的情况。

比较次数和总列表长度的奇偶性还有确定中位数位置是有关联性的，这一点可以自己在下面例子里尝试一下。

1.当allsize为奇数时：只存在一个中位数，此时比较次数为 allsize/2 次

(1).p1、p2在中间位置

        [1,2,3,8,9] 和 [4,5,6,7] ，总列表 [1,2,3,4,5,6,7,8,9]

        总长度为9，比较4次：

                第一次 p1->1，p2->4，p1<p2，p1++;

                第二次 p1->2，p2->4，p1<p2，p1++;

                第三次 p1->3，p2->4，p1<p2，p1++;

                第四次 p1->8，p2->4，p1>p2，p2++;

                此时：p1->8，p2->5 取二者较小值为5，中位数为5

(2).p1在arr1末尾，并且p1<=p2时

        [1,2,3,4]和[5,6,7,8,9]，总列表 [1,2,3,4,5,6,7,8,9]

        总长度为9，比较4次：

                第一次 p1->1，p2->5，p1<p2，p1++;

                第二次 p1->2，p2->5，p1<p2，p1++;

                第三次 p1->3，p2->5，p1<p2，p1++;

                第四次 p1->4，p2->5，p1<p2，此时p1已经在末尾，不再++，设置变量标记中位数在arr2中（p2侧）;

                此时：直接取p2为中位数，中位数为5

(3).p1在arr1末尾，并且p1>p2时

        [1,2,3,5]和[4,6,7,8,9]，总列表 [1,2,3,4,5,6,7,8,9]

        总长度为9，比较4次：

                第一次 p1->1，p2->4，p1<p2，p1++;

                第二次 p1->2，p2->4，p1<p2，p1++;

                第三次 p1->3，p2->4，p1<p2，p1++;

                第四次 p1->5，p2->4，p1>p2，此时p2++;

                此时：p1->5，p2->6 取p1、p2二者较小值，中位数为5

2.当allsize为偶数时，中位数等于中间两个元素取平均值，此时两个元素比较次数为 allsize/2 -1 次，执行完allsize/2 -1 次判断时： 

(1).p1、p2在中间位置，并不能确定中间两个数在哪一侧产生，可能是两侧各贡献一个（包括p1或者p2没有发生移动的情况）

        两侧各贡献一个：

        （这种情况牛客里面的测试用例没有覆盖这种情况，刚开始我写的代码这部分有缺陷，所以会出现问题，下面的代码实现已经补上了处理策略，判断过程看下面加粗黄色说明部分）

        [1,2,3,8,9] 和 [4,5,6,7,10] ，总列表 [1,2,3,4,5,6,7,8,9,10]

        总长度为10，比较4次：

                第一次 p1->1，p2->4，p1<p2，p1++;

                第二次 p1->2，p2->4，p1<p2，p1++;

                第三次 p1->3，p2->4，p1<p2，p1++;

                第四次 p1->8，p2->4，p1>p2，p2++;

                此时：p1->8，p2->5，最后一次移动的是p2（作为求平均数的左值），且p2未到达末尾，需要比较(p2+1)和p1位置的值，(p2+1)->6，p1->8，取二者较小值为6，中位数为(5+6)/2=5.5

        

        [4,5,6,7,10] 和 [1,2,3,8,9] ，总列表 [1,2,3,4,5,6,7,8,9,10]

        总长度为10，比较4次：

                第一次 p2->4，p1->1，p1>p2，p2++;

                第二次 p1->4，p2->2，p1>p2，p2++;

                第三次 p1->4，p2->3，p1>p2，p2++;

                第四次 p1->4，p2->8，p1<p2，p1++;

                此时：p1->5，p2->8，最后一次移动的是p1（作为求平均数的左值），且p1未到达末尾，需要比较(p1+1)和p2位置的值，(p1+1)->6，p1->8，取二者较小值为6，中位数为(5+6)/2=5.5

---

        p1或者p2没有发生移动的情况：

        [1,2,3,7]和[4,5,8,9]，总列表 [1,2,3,4,5,7,8,9]

        总长度为8，比较3次：

                第一次 p1->1，p2->4，p1<p2，p1++;

                第二次 p1->2，p2->4，p1<p2，p1++;

                第三次 p1->3，p2->4，p1<p2，p1++;

                此时：p1->7，p2->4  需要比较一下p1和p2+1位置的大小，如果p1>p2+1，中位数选择p2和p2+1位置元素和的平均值；如果p1<p2+1，中位数选择p1和p2的平均值。

                

        [4,5,8,9] 和 [1,2,3,7]，总列表 [1,2,3,4,5,7,8,9]

        总长度为8，比较3次：

                第一次 p1->4，p2->1，p1>p2，p2++;

                第二次 p1->4，p2->2，p1>p2，p2++;

                第三次 p1->4，p2->3，p1>p2，p2++;

                此时：p1->4，p2->7 需要比较一下p2和p1+1位置的大小，如果p2>p1+1，中位数选择p1和p1+1位置元素和的平均值；如果p2<p1+1，中位数选择p1和p2的平均值。

---

        并不能确定是否只出现在一侧的情况：

        [1,8] 和 [4,5,6,7,8,9]，总列表 [1,4,5,6,7,8,8,9]

        总长度为8，比较3次：

                第一次 p1->1，p2->4，p1<p2，p1++;

                第二次 p1->8到达末尾，p2->4，p1>p2，p2++;

                第三次 p1->8到达末尾，p2->5，p1>p2，p2++;

                此时：p1->8，p2->6  p1到达末尾，p2一定是中间两个数之一，需要比较一下p2+1和p1的大小，取较小值作为另一个数，p2+1->7，p1->8，取p2+1和p2的平均数作为中位数，值为6.5。

(2).p1早已到达arr1末尾，确定两个数确定在p2侧产生

         [6,7] 和 [5,9,10,11,12,13]，总列表 [5,6,7,9,10,11,12,13]

        总长度为8，比较3次：

                第一次 p1->6，p2->5，p1>p2，p2++;

                第二次 p1->6，p2->9，p1<p2，p1++;

                第三次 p1->7到达末尾，p2->9，p1<p2，p2++，且设置标志位；

                此时：中间两个数只会是p2和p2+1位置的值，计算两个数的平均数：p2->9，(p2+1)->10，平均值为8.5。

(3).p2早已到达arr2末尾，中间两个数确定在p1侧产生，这个执行过程大家自己根据上面(2)的过程推理一下。

       [5,9,10,11,12,13] 和 [6,7]，总列表 [5,6,7,9,10,11,12,13]

三、代码实现

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums1 int整型ArrayList* @param nums2 int整型ArrayList* @return double浮点型*/public double Median (ArrayList<Integer> nums1, ArrayList<Integer> nums2) {double res = 0;int allsize = nums1.size() + nums2.size();int mididx = allsize / 2;int icounter=0;boolean oddnum=false;//奇数数if(allsize%2!=0){oddnum=true;//此时根据side判断取哪一侧的值，如果没有出现倾斜情况，则取p1、p2较小值icounter=mididx;}else{oddnum=false;//此时取p1和p2位置平均值icounter=mididx-1;}int p1 = 0, p2 = 0;boolean p1side=false,p2side=false;int lastestmove=0;while (icounter > 0) {if (p1 < (nums1.size() - 1) && nums1.get(p1) <= nums2.get(p2)) {p1++;lastestmove=1;}else if(p1 == (nums1.size() - 1)){if(!oddnum){if(!p2side&&nums1.get(p1)>nums2.get(p2)){p2++;lastestmove=2;}else if(!p2side&&nums1.get(p1)<=nums2.get(p2)){p2side=true;}else{p2++;lastestmove=2;}    }else{if(!p2side&&nums1.get(p1)>nums2.get(p2)){p2++;lastestmove=2;}else{if(!p2side){p2side=true;}else{p2++;lastestmove=2;}}}}else if (p2 < (nums2.size() - 1) && nums1.get(p1) > nums2.get(p2)) {p2++;lastestmove=2;}else if (p2 == (nums2.size() - 1)) {if(!oddnum){if(!p1side&&nums2.get(p2)>=nums1.get(p1)){p1++;lastestmove=1;}else if(!p1side&&nums2.get(p2)<nums1.get(p1)){p1side=true;}else{p1++;lastestmove=1;}    }else{if(!p1side&&nums2.get(p2)>nums1.get(p1)){p1++;lastestmove=1;}else{if(!p1side){p1side=true;}else{p1++;lastestmove=1;}}}}icounter--;}if (!oddnum) { //此时取中间两个值的平均数为中位数if(p1side){//中间两个数位于p1侧res=((double)(nums1.get(p1)) + (double)(nums1.get(p1+1))) / 2;}else if(p2side){//中间两个数位于p2侧res=((double)(nums2.get(p2)) + (double)(nums2.get(p2+1))) / 2;}else{double minright=(double)(nums2.get(p2));double minleft=(double)(nums1.get(p1));if(lastestmove==1){//此时p1为左值//偶数个数时，当最后一次移动发生在p1侧且p1侧没有到达末尾，比较p1+1和p2大小，取较小值作为右值minleft=(double)(nums1.get(p1));minright=nums1.get(p1+1)>nums2.get(p2)?nums2.get(p2):nums1.get(p1+1);}else if(lastestmove==2){//此时p2为右值//原理同上，比较p2+1和p1大小，取较小值minleft=(double)(nums2.get(p2));minright=nums2.get(p2+1)>nums1.get(p1)?nums1.get(p1):nums2.get(p2+1);}res=( minleft + minright) / 2;}} else { //此时取p1、p2两者较小的值if(p1side){res = nums1.get(p1);}else if(p2side){res = nums2.get(p2);}else{res = Math.min(nums2.get(p2),nums1.get(p1));}}return res;}
}

四、刷题链接

两个升序数组的中位数_牛客题霸_牛客网

五、近似题目

数组-在两个长度相等的有序数组中找到上中位数-CSDN博客文章浏览阅读272次，点赞4次，收藏6次。java刷题：查找两个长度相等的有序数组中的上中位数。https://blog.csdn.net/hehe_soft_engineer/article/details/139200124?spm=1001.2014.3001.5502