首页 > 代码库 > 排序练习题（六）：相邻两数最大差值
排序练习题（六）：相邻两数最大差值
有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。
给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素多于1个。
测试样例：
[1,2,5,4,6],5
返回：2
public class Gap { public int maxGap(int[] A, int n) { // write code here if(null == A ||n<2) return 0; int min=Integer.MAX_VALUE; int max=Integer.MIN_VALUE; for(int i=0;i<n;i++){ if(A[i]>max) max=A[i]; if(A[i]<min) min=A[i]; } if(min==max) return 0; boolean[] hasNum =new boolean[n+1]; int[]maxs=new int[n+1]; int[] mins=new int[n+1]; for(int i=0;i<n;i++){ int bid=bucket(A[i],n,min,max); maxs[bid]=hasNum[bid]?Math.max(maxs[bid],A[i]):A[i]; mins[bid]=hasNum[bid]?Math.min(mins[bid],A[i]):A[i]; hasNum[bid]=true; } int res=0; int lastMax=0; int i=0; while(i<=n){ if(hasNum[i++]){ lastMax = maxs[i-1]; break; } } for(;i<=n;i++){ if(hasNum[i]){ res=Math.max(res,mins[i]-lastMax); lastMax=maxs[i]; } } return res; } public int bucket(long num,long length,long min,long max){ return (int)((num-min)*length/(max-min)); }}
排序练习题（六）：相邻两数最大差值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。