软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 研发管理 -> 减治算法之寻找第K小元素问题 -> 正文阅读

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


一、问题描述
给定一个整数数列,寻找其按递增排序后的第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  
研发管理 最新文章
拉格朗日乘数
maven之可视化项目依赖(Visualizingdepend
mac效率工具
Atitit.css规范bem项目中CSS的组织和管理
git入门
Asimplemodelfordescribingbasicsourcesofp
Linux进程管理浅析
我的openwrt学习笔记(十九):linux便捷开
2、微控制器选择
Git使用手册:为Git仓库创建Submodule
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年1日历
2018-1-23 4:03:49
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --