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

[研发管理]减治算法之寻找第K小元素问题

  2016-03-24 00:00:48

一、问题描述
给定一个整数数列,寻找其按递增排序后的第k个位置上的元素。
二、问题分析

三、算法代码

public static int selectMinK(int [] arr, int low, int high, int k){
		int index = pation(arr, low, high);
		if(index == k){
			return arr[index];
		}
		if(index < k){
			return selectMinK(arr, index + 1, high, k);
		}else{
			return selectMinK(arr, low, index - 1, k);
		}
	}
	
	public static int pation(int [] arr, int low, int high){
		while(low < high){
			while(low < high && arr[low] <= arr[high]){
				high--;
			}
			if(low < high){
				int tmp = arr[low];
				arr[low] = arr[high];
				arr[high] = tmp;
				low++;
			}
			while(low < high && arr[low] <= arr[high]){
				low++;
			}
			if(low < high){
				int tmp = arr[low];
				arr[low] = arr[high];
				arr[high] = tmp;
				high--;
			}
		}
		return low;
	}
四、完整测试代码

public class Solution {
	
	public static void main(String [] args){
		int [] randArr = new int[]{5,2,8,6,3,6,9,7};
		int result = selectMinK(randArr, 0, randArr.length - 1, 4);
		System.out.print(result);
	}
	public static int selectMinK(int [] arr, int low, int high, int k){
		int index = pation(arr, low, high);
		if(index == k){
			return arr[index];
		}
		if(index < k){
			return selectMinK(arr, index + 1, high, k);
		}else{
			return selectMinK(arr, low, index - 1, k);
		}
	}
	
	public static int pation(int [] arr, int low, int high){
		while(low < high){
			while(low < high && arr[low] <= arr[high]){
				high--;
			}
			if(low < high){
				int tmp = arr[low];
				arr[low] = arr[high];
				arr[high] = tmp;
				low++;
			}
			while(low < high && arr[low] <= arr[high]){
				low++;
			}
			if(low < high){
				int tmp = arr[low];
				arr[low] = arr[high];
				arr[high] = tmp;
				high--;
			}
		}
		return low;
	}
}
五、运行结果

第4小元素为:6

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