如何做网站的注册页面,建设部特种作业证网站查询,设计官网公司,烟台建设集团 招聘信息网站一、题目描述 二、解题思路
(一).基本思想#xff1a;
如果列表总长度allsize( arr1.size()arr2.size() ) 为奇数时#xff0c;中位数位置应该在两个列表排序后的第 allsize/2 位置处#xff0c;如果allsize为偶数#xff0c;中位数应该取 (allsize/2)-1 和 allsize/2 的…一、题目描述 二、解题思路
(一).基本思想
如果列表总长度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-1p2-4p1p2p1; 第二次 p1-2p2-4p1p2p1; 第三次 p1-3p2-4p1p2p1; 第四次 p1-8p2-4p1p2p2; 此时p1-8p2-5 取二者较小值为5中位数为5
(2).p1在arr1末尾并且p1p2时 [1,2,3,4]和[5,6,7,8,9]总列表 [1,2,3,4,5,6,7,8,9] 总长度为9比较4次 第一次 p1-1p2-5p1p2p1; 第二次 p1-2p2-5p1p2p1; 第三次 p1-3p2-5p1p2p1; 第四次 p1-4p2-5p1p2此时p1已经在末尾不再设置变量标记中位数在arr2中p2侧; 此时直接取p2为中位数中位数为5
(3).p1在arr1末尾并且p1p2时 [1,2,3,5]和[4,6,7,8,9]总列表 [1,2,3,4,5,6,7,8,9] 总长度为9比较4次 第一次 p1-1p2-4p1p2p1; 第二次 p1-2p2-4p1p2p1; 第三次 p1-3p2-4p1p2p1; 第四次 p1-5p2-4p1p2此时p2; 此时p1-5p2-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-1p2-4p1p2p1; 第二次 p1-2p2-4p1p2p1; 第三次 p1-3p2-4p1p2p1; 第四次 p1-8p2-4p1p2p2; 此时p1-8p2-5最后一次移动的是p2作为求平均数的左值且p2未到达末尾需要比较(p21)和p1位置的值(p21)-6p1-8取二者较小值为6中位数为(56)/25.5 [4,5,6,7,10] 和 [1,2,3,8,9] 总列表 [1,2,3,4,5,6,7,8,9,10] 总长度为10比较4次 第一次 p2-4p1-1p1p2p2; 第二次 p1-4p2-2p1p2p2; 第三次 p1-4p2-3p1p2p2; 第四次 p1-4p2-8p1p2p1; 此时p1-5p2-8最后一次移动的是p1作为求平均数的左值且p1未到达末尾需要比较(p11)和p2位置的值(p11)-6p1-8取二者较小值为6中位数为(56)/25.5 p1或者p2没有发生移动的情况 [1,2,3,7]和[4,5,8,9]总列表 [1,2,3,4,5,7,8,9] 总长度为8比较3次 第一次 p1-1p2-4p1p2p1; 第二次 p1-2p2-4p1p2p1; 第三次 p1-3p2-4p1p2p1; 此时p1-7p2-4 需要比较一下p1和p21位置的大小如果p1p21中位数选择p2和p21位置元素和的平均值如果p1p21中位数选择p1和p2的平均值。 [4,5,8,9] 和 [1,2,3,7]总列表 [1,2,3,4,5,7,8,9] 总长度为8比较3次 第一次 p1-4p2-1p1p2p2; 第二次 p1-4p2-2p1p2p2; 第三次 p1-4p2-3p1p2p2; 此时p1-4p2-7 需要比较一下p2和p11位置的大小如果p2p11中位数选择p1和p11位置元素和的平均值如果p2p11中位数选择p1和p2的平均值。 并不能确定是否只出现在一侧的情况 [1,8] 和 [4,5,6,7,8,9]总列表 [1,4,5,6,7,8,8,9] 总长度为8比较3次 第一次 p1-1p2-4p1p2p1; 第二次 p1-8到达末尾p2-4p1p2p2; 第三次 p1-8到达末尾p2-5p1p2p2; 此时p1-8p2-6 p1到达末尾p2一定是中间两个数之一需要比较一下p21和p1的大小取较小值作为另一个数p21-7p1-8取p21和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-6p2-5p1p2p2; 第二次 p1-6p2-9p1p2p1; 第三次 p1-7到达末尾p2-9p1p2p2且设置标志位 此时中间两个数只会是p2和p21位置的值计算两个数的平均数p2-9(p21)-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 (ArrayListInteger nums1, ArrayListInteger nums2) {double res 0;int allsize nums1.size() nums2.size();int mididx allsize / 2;int icounter0;boolean oddnumfalse;//奇数数if(allsize%2!0){oddnumtrue;//此时根据side判断取哪一侧的值如果没有出现倾斜情况则取p1、p2较小值icountermididx;}else{oddnumfalse;//此时取p1和p2位置平均值icountermididx-1;}int p1 0, p2 0;boolean p1sidefalse,p2sidefalse;int lastestmove0;while (icounter 0) {if (p1 (nums1.size() - 1) nums1.get(p1) nums2.get(p2)) {p1;lastestmove1;}else if(p1 (nums1.size() - 1)){if(!oddnum){if(!p2sidenums1.get(p1)nums2.get(p2)){p2;lastestmove2;}else if(!p2sidenums1.get(p1)nums2.get(p2)){p2sidetrue;}else{p2;lastestmove2;} }else{if(!p2sidenums1.get(p1)nums2.get(p2)){p2;lastestmove2;}else{if(!p2side){p2sidetrue;}else{p2;lastestmove2;}}}}else if (p2 (nums2.size() - 1) nums1.get(p1) nums2.get(p2)) {p2;lastestmove2;}else if (p2 (nums2.size() - 1)) {if(!oddnum){if(!p1sidenums2.get(p2)nums1.get(p1)){p1;lastestmove1;}else if(!p1sidenums2.get(p2)nums1.get(p1)){p1sidetrue;}else{p1;lastestmove1;} }else{if(!p1sidenums2.get(p2)nums1.get(p1)){p1;lastestmove1;}else{if(!p1side){p1sidetrue;}else{p1;lastestmove1;}}}}icounter--;}if (!oddnum) { //此时取中间两个值的平均数为中位数if(p1side){//中间两个数位于p1侧res((double)(nums1.get(p1)) (double)(nums1.get(p11))) / 2;}else if(p2side){//中间两个数位于p2侧res((double)(nums2.get(p2)) (double)(nums2.get(p21))) / 2;}else{double minright(double)(nums2.get(p2));double minleft(double)(nums1.get(p1));if(lastestmove1){//此时p1为左值//偶数个数时当最后一次移动发生在p1侧且p1侧没有到达末尾比较p11和p2大小取较小值作为右值minleft(double)(nums1.get(p1));minrightnums1.get(p11)nums2.get(p2)?nums2.get(p2):nums1.get(p11);}else if(lastestmove2){//此时p2为右值//原理同上比较p21和p1大小取较小值minleft(double)(nums2.get(p2));minrightnums2.get(p21)nums1.get(p1)?nums1.get(p1):nums2.get(p21);}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?spm1001.2014.3001.5502
