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

2024-05-28 01:28
文章标签 数组 两个 中位数 升序

本文主要是介绍数组-两个升序数组中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目描述

二、解题思路

(一).基本思想：

如果列表总长度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

这篇关于数组-两个升序数组中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1009154。

相关文章

hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
两个月冲刺软考——访问位与修改位的题型(淘汰哪一页)；内聚的类型；关于码制的知识点；地址映射的相关内容

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页)；内聚的类型；关于码制的知识点；地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位：为1时表示在内存期间被访问过，为0时表示未被访问；修改位：为1时表示该页面自从被装入内存后被修改过，为0时表示未修改过。 置换页面时，最先置换访问位和修改位为00的，其次是01(没被访问但被修改过)的，之后是10(被访问了但没被修改过)，最后是11。 2.内聚的类型 功能内聚：完成一个单一功能，各个部分协同工作，缺一不可。 顺序内聚：
阅读更多...
C语言：柔性数组

C语言：柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t；t = malloc(sizeof(Test) + 11);strcpy(t->arr,
阅读更多...
C 语言基础之数组

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组，顾名思义，就是一组数。 假如班上有 30 个同学，让你编程统计每个人的分数，求最高分、最低分、平均分等。如果不知道数组，你只能这样写代码： int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou
阅读更多...
计算数组的斜率，偏移，R2

计算数组的斜率，偏移，R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou
阅读更多...
C# double[] 和Matlab数组MWArray[]转换

C# double[] 和Matlab数组MWArray[]转换

C# double[] 转换成MWArray[], 直接赋值就行             MWNumericArray[] ma = new MWNumericArray[4];             double[] dT = new double[] { 0 };             double[] dT1 = new double[] { 0,2 };
阅读更多...
PHP7扩展开发之数组处理

PHP7扩展开发之数组处理

前言 这次，我们将演示如何在PHP扩展中如何对数组进行处理。要实现的PHP代码如下： <?phpfunction array_concat ($arr, $prefix) {foreach($arr as $key => $val) {if (isset($prefix[$key]) && is_string($val) && is_string($prefix[$key])) {$arr[
阅读更多...
Go 数组赋值问题

Go 数组赋值问题

package mainimport "fmt"type Student struct {Name stringAge int}func main() {data := make(map[string]*Student)list := []Student{{Name:"a",Age:1},{Name:"b",Age:2},{Name:"c",Age:3},}// 错误 都指向了最后一个v// a
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2