首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >桶排序的算法

桶排序的算法

作者头像
曼路
发布2018-10-18 15:22:42
3670
发布2018-10-18 15:22:42
举报
文章被收录于专栏:浪淘沙浪淘沙

1.求一个无序数组排好序后,相邻元素差值最大为多少,时间复杂度为O(N)

思路:设数组的长度为len,创建三个长度为len+1的(桶)数组。将数组的元素根据大小放在不同的桶中,其中,必定有差值大于一个桶的差存在,故同一个桶中不可能出现差值最大的。三个数组,一个为maxs,一个为mins,一个为hasNum.

package algorithm;
/**
 * 求一个无序数组排好序后,相邻元素差值最大为多少,时间复杂度为O(N)
 * 用桶排序
 * @author hasee
 *
 */
public class MaxGap {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {1,8,3,6,8,0,4,13,16};
		int res = maxGap(arr);
		System.out.println(res);
	}
	public static int maxGap(int[] arr) {
		if(arr==null||arr.length<2) { 
			return 0;
		}
		int len = arr.length;
		int min = Integer.MAX_VALUE;
		int max= Integer.MIN_VALUE;
		
		for(int i = 0;i < len;i++) {
			min = Math.min(arr[i], min);
			max = Math.max(arr[i], max);
		}
		if(min == max) {
			return 0;
		}
		boolean[] hasNum = new boolean[len+1];
		int[] mins = new int[len+1];
		int[] maxs = new int[len+1];
		int bid = 0;
		for(int j = 0;j < len;j++) {
			bid = bucket(arr[j],len,min,max); 
			//System.out.println(bid);
			mins[bid] = hasNum[bid]?Math.min(arr[j], mins[bid]):arr[j];
			maxs[bid] = hasNum[bid]?Math.max(arr[j], maxs[bid]):arr[j];
			hasNum[bid] = true;
		}
		//开始计算差值
		int res = 0;
		int lastMax = maxs[0];
		int i =1;
		for(;i<=len;i++) {
			if(hasNum[i]){
			res  = Math.max(res,mins[i]-lastMax);
			lastMax = maxs[i];
			}
		}
		return res;
		
	}
	private static int bucket(int i, int len, int min, int max) {
		// TODO Auto-generated method stub
		return (i-min)*len/(max-min);
	} 

}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年07月13日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档