初中的数学书上说,当数据的个数是奇数时,中位数只有一个,当数据的个数为偶数时,中位数有两个:左中位数和右中位数。这个题根据题意,应该是求左中位数。
方法一:时间复杂度O(n/2), 空间复杂度O(1)
用两个变量跟踪两个数组,当走到L次的时候就是中位数了,即省了空间时间又减半了。
这是最容易想到也最易实现的了:
public class Test1{
static void GetMiddleNum(int[] a ,int[] b){
int aindex=0;
int bindex=0;
for(int i=0;i<a.length;i++){
if(a[aindex]<b[bindex]){
if(aindex+bindex==a.length-1){
System.out.println(a[aindex]);
break;
}
aindex++;
}else{
if(aindex+bindex==a.length-1){
System.out.println(b[bindex]);
break;
}
bindex++;
}
}
}
public static void main(String[] args){
int a[] = {11,13,15,17,19};
int b[] = {2,4,6,8,20};
int mid;
GetMiddleNum(a,b);
int ar1[] = {1, 2, 6, 8};
int ar2[] = {3, 4, 8, 10};
GetMiddleNum(ar1,ar2);
}
}
运行:
C:\ex>java Test1
11
4
方法二:暂且叫它二分法.时间复杂度O(logn),空间复杂度O(1)
(网上有很多版本,测试后发现都有问题,下面这个我认为是正解:来自:http://blog.csdn.net/algorithm_only/article/details/7084478)
分别求出序列A 和B 的中位数,设为a 和b,求序列A 和B 的中位数过程如下:
1)若a=b,则a 或b 即为所求中位数,算法结束。
2)若a<b,则舍弃序列A 中较小的一半,同时舍弃序列B 中较大的一半,要求舍弃的长度相等;
3)若a>b,则舍弃序列A 中较大的一半,同时舍弃序列B 中较小的一半,要求舍弃的长度相等;
在保留的两个升序序列中,重复过程1)、2)、3),直到两个序列中只含一个元素时为止,较小者即为所求的中位数。
public class Test{
static int getMedian(int a[], int b[], int n) {
int start1 = 0, end1 = n-1, m1;
int start2 = 0, end2 = n-1, m2;
while (start1 != end1 || start2 != end2) {
m1 = (start1 + end1) / 2;
m2 = (start2 + end2) / 2;
if (a[m1] == b[m2])
return a[m1];
if (a[m1] < b[m2]) {
if ((start1+end1) % 2 == 0) {
start1 = m1;
end2 = m2;
} else {
start1 = m1 + 1;
end2 = m2;
}
} else {
if ((start1+end1) % 2 == 0) {
end1 = m1;
start2 = m2;
} else {
end1 = m1;
start2 = m2 + 1;
}
}
}
return a[start1] < b[start2] ? a[start1] : b[start2];
}
public static void main(String[] args){
int ar1[] = {11, 13, 15, 17,19};
int ar2[] = {2, 4, 6, 8, 20};
System.out.printf("Median is %d", getMedian(ar1, ar2, 5));
int a[]={1,2,6,8};
int b[]={3,4,10,20};
System.out.printf("Median is %d", getMedian(a, b, 4));
}
}
运行:
C:\ex>java Test
Median is 11
Median is 4
- 大小: 49.6 KB
分享到:
相关推荐
综上所述,这份2011年的计算机考研真题覆盖了计算机科学与技术学科联考计算机学科专业基础综合的多个重要知识点。掌握这些知识点对于考生在考研中取得好成绩至关重要,同时也为考生未来在计算机领域的工作和研究打下...
2011年计算机考研统考真题及详细解析
2009,2010,2011计算机考研真题及参考答案完整版__考研必备.doc
在深入探讨2011年燕山大学计算机考研试题这一主题前,我们首先需要了解燕山大学计算机专业考研的基本情况,以及考研试题的重要性。燕山大学位于河北省秦皇岛市,是一所具有悠久历史和良好学术声誉的高等学府,其...
在2011年的计算机考研真题中,还涉及了数据结构和算法的知识。例如,题目中提到了完全二叉树的问题,完全二叉树是一种特殊的二叉树,其中除了最后一层外,每一层都被完全填满,并且所有的结点都尽可能地集中在左边。...
2011年计算机考研真题涵盖了计算机专业基础知识的多个领域,包括数据结构、算法、计算机网络、操作系统、计算机组成原理、编译原理、数据库以及软件工程等。以下是对部分知识点的详细解析: 1. 时间复杂度:在程序...
从给定的文件信息来看,主要涉及的是2011年南京邮电大学计算机考研试题的相关内容。南京邮电大学是一所具有深厚信息技术背景的高校,其计算机专业在全国范围内享有较高的声誉。考研试题通常涵盖了该学科的核心知识点...
本压缩包文件“09、10年的计算机考研真题和2011计算机专业考研大纲”正是为备考者提供了一份宝贵的参考资料。 首先,我们来看“考研大纲”。大纲是考试的指挥棒,它明确了考试的目标、范围和重点。2011年计算机专业...
从提供的文件内容中,我们可以看到一系列计算机科学和技术相关的知识点。由于文档内容不连贯、包含大量数字和字母组合以及一些可能由于OCR扫描错误导致的杂乱字符,因此需要我们从中提炼出有意义的信息和概念。下面...
《2011计算机考研大纲》是针对全国硕士研究生入学统一考试中计算机科学与技术学科联考的专业基础综合考试所制定的重要指导文件。这个大纲详细规定了考试的范围、目标和要求,对于备考的学生来说,它是了解考试内容、...
本文总结了大连理工大学2011年计算机考研复试的真题内容,涵盖了笔试和面试两部分。笔试部分共四门:计算机系统结构、软件工程、C/C++语言和数据库。每门科目都涵盖了基础知识点,难度不高,但笔试成绩对考研结果的...
【知识点详解】 ...总结:本文主要介绍了计算机操作系统中的关键概念,包括进程调度算法、处理机状态、线程模型以及I/O操作流程和控制方式。理解这些知识点对于深入学习计算机科学,尤其是操作系统设计至关重要。
吉林大学2011年计算机考研真题.part2
计算机考研2011-2018川大874真题.rar
4. **2009-2011计算机考研真题及答案(含选择题解析)** 这份综合性的文档不仅包含了2009年至2011年的全部真题,还特别提供了选择题的解析。选择题是计算机考研中常见的题型,涵盖的知识面广,解析可以帮助考生深入...