软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 研发管理 -> 减治算法之寻找两个递增序列的中位数 -> 正文阅读
研发管理 最新文章
拉格朗日乘数
maven之可视化项目依赖(Visualizingdepend
mac效率工具
Atitit.css规范bem项目中CSS的组织和管理
git入门
Asimplemodelfordescribingbasicsourcesofp
Linux进程管理浅析
我的openwrt学习笔记(十九):linux便捷开
2、微控制器选择
Git使用手册:为Git仓库创建Submodule

[研发管理]减治算法之寻找两个递增序列的中位数

  2016-03-26 16:29:53

一、问题描述
寻找两个递增序列的中位数。
本算法中只能解决两个序列长度规模相等的问题,若两个序列长度规模不相等,则可以先做合并(leetcode:Merge Sorted Array 【Java】)后再寻找中位数。
二、问题分析
分别计算序列A,B的中位数a,b


比较中位数a,b,会出现以下三种请款
(1)a = b,直接返回结果a
(2)a < b,两个序列的中位数只能出现在[a,b),在序列中A中删除a之前的元素形成新序列A,在序列B中删除b之后的元素形成新序列B
(3)a > b,两个序列的中位数只能出现在[b,a),在序列中A中删除a之后的元素形成新序列A,在序列B中删除b之前的元素形成新序列B


重复以上步骤。
三、算法代码

public static int searchMid(int [] a, int [] b){
		if(a.length != b.length){
			System.out.println("序列规模不一致,计算结果初始化为-1!");
			return -1;
		}
		int s1 = 0;
		int e1 = a.length - 1;
		int s2 = 0;
		int e2 = b.length - 1;
		int mid1,mid2;
		while(s1 < e1 && s2 < e2){
			mid1 = (s1 + e1) / 2;
			mid2 = (s2 + e2) / 2;
			if(a[mid1] == b[mid2]){
				return a[mid1];
			}
			if(a[mid1] < b[mid2]){
				s1 = mid1 + 1;
				e2 = mid2;
			}else{
				s2 = mid2 + 1;
				e1 = mid1;
			}
		}
		if(a[s1] < b[s2]){
			return a[s1];
		}else{
			return b[s2];
		}
	}
四、完整测试代码

public class package01 {

	public static void main(String [] args){
		int [] a = new int[]{1,2,3,4,5,11,13};
		int [] b = new int[]{6,7,8,9,10,12,14};
		int result = searchMid(a, b);
		System.out.print("两个递增序列的中位数为:" + result);
	}

	public static int searchMid(int [] a, int [] b){
		if(a.length != b.length){
			System.out.println("序列规模不一致,计算结果初始化为-1!");
			return -1;
		}
		int s1 = 0;
		int e1 = a.length - 1;
		int s2 = 0;
		int e2 = b.length - 1;
		int mid1,mid2;
		while(s1 < e1 && s2 < e2){
			mid1 = (s1 + e1) / 2;
			mid2 = (s2 + e2) / 2;
			if(a[mid1] == b[mid2]){
				return a[mid1];
			}
			if(a[mid1] < b[mid2]){
				s1 = mid1 + 1;
				e2 = mid2;
			}else{
				s2 = mid2 + 1;
				e1 = mid1;
			}
		}
		if(a[s1] < b[s2]){
			return a[s1];
		}else{
			return b[s2];
		}
	}
}
五、运行结果

两个递增序列的中位数为:8

上一篇文章      下一篇文章      查看所有文章
2016-03-26 16:29:39  
360图书馆 论文大全 母婴/育儿 软件开发资料 网页快照 文字转语音 购物精选 软件 美食菜谱 新闻中心 电影下载 小游戏 Chinese Culture
生肖星座解梦 三沣玩客 拍拍 视频 开发 Android开发 站长 古典小说 网文精选 搜图网 天下美图 中国文化英文 多播视频 装修知识库
2017-1-19 18:48:10
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --