请设计一个复杂度为O(n)的算法，计算一个未排序数组中排序后相邻元素的最大差值。
给定一个整数数组A和数组的大小n，请返回最大差值。保证数组元素个数大于等于2小于等于500。
测试样例：
[9,3,1,10],4
返回：6
[编程题]相邻最大差值
利用桶排序的思想，
import java.util.*;
public class MaxDivision {
public int findMaxDivision(int[] A, int n) {
// write code here
if (A == null || A.length < 2) {
return 0;
}
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) { // 找到数组的最小值和最大值
if (A[i] < min) {
min = A[i];
}
if (A[i] > max) {
max = A[i];
}
}
if (min == max) {
return 0;
}
boolean[] hasNum = new boolean[n + 1]; // 标识桶中是否有数
int[] bMins = new int[n + 1]; // 桶中最小值
int[] bMaxs = new int[n + 1]; // 桶中最大值
for (int i = 0; i < n; i++) { // 统计每个桶中的最小值和最大值
int b = mapToBucket(A[i], n, min, max); // 当前元素所在的桶
if (hasNum[b]) {
if (A[i] < bMins[b]) {
bMins[b] = A[i];
}
if (A[i] > bMaxs[b]) {
bMaxs[b] = A[i];
}
} else {
bMins[b] = bMaxs[b] = A[i];
hasNum[b] = true;
}
}
int maxGap = 0;
int lastbMax = bMaxs[0]; // 前一个非空桶的最大值，第一个非空桶必是0号桶
int b = 1;
while (b <= n) {
if (hasNum[b]) {
if (bMins[b] - lastbMax > maxGap) { // 当前非空桶的最小值与上一个非空桶的最大值做差，取最大差值
maxGap = bMins[b] - lastbMax;
}
lastbMax = bMaxs[b];
}
b++;
}
return maxGap;
}
/**
* 映射函数，将数组元素映射到桶中，使用long类型防止相乘时溢出
*
* @param num
* @param n
* @param min
* @param max
* @return
*/
public int mapToBucket(long num, long n, long min, long max) {
return (int) ((num - min) * n / (max - min));
}
}
发表于 2017-08-06 11:57:54
回复(3)
思路：因为要控制复杂度为O（n），所以用排序是不满足题意的。我的思路是，先求出数组中的最大与最小数，之后建立一个最大减最小这个范围大小的数组，再往数组中填充数字。再计算这个数组中连续为0的最大间隔。例如：A={9,3,1,10},求出最大值为10，最小值为1，即可建立一个10 - 1 + 1 = 10 这么大的数组temp[10],因为A[]数组中的数的范围都在1~10之间，那我们可以在temp[0]=1,temp[2]=1,temp[8]=1,temp[9]=1，即{1,0,1,0,0,0,0,0,1,1}，这最大差值即为temp[2]到temp[8]的距离6，返回6;publicclassMaxDivision {publicintfindMaxDivision(int[] A, intn) {intmax = Integer.MIN_VALUE, min = Integer.MAX_VALUE;for(inti = 0; i < A.length; i++) {if(A[i] > max)max = A[i];if(A[i] < min)min = A[i];}if(max == min) return0;int[] temp = newint[max - min + 1];for(inti = 0; i < A.length; i++) {temp[A[i] - min] = temp[A[i] - min] + 1;}intrs = 0;intcur = 0;for(inti = 1; i < temp.length; i++) {if(temp[i] == 0) {cur ++;} else{cur ++;if(cur > rs) {rs = cur;}cur = 0;}}returnrs;}}
发表于 2017-04-21 19:38:30
回复(5)
回答说STL里的sort不满足要求，那么我们就用STL里的堆排序，heap_sort()，按理说堆排序空间复杂度O(nlogn)，时间复杂度O(1)，应该是满足要求的
int findMaxDivision(vector<int> A, int n) {
make_heap(A.begin(),A.end());
sort_heap(A.begin(),A.end());
int max = 0,tmp;
for(int i=1;i<n;i++)
{
tmp = A[i]-A[i-1];
max = tmp>max ? tmp:max;
}
return max;
}
发表于 2016-09-05 10:09:39
回复(7)
class MaxDivision {
public:
int findMaxDivision(vector<int> A, int n) {
// write code here
//计数排序--虽然我感觉不适合，因为当数组的（最大值-最小值）很大时，就不是O(n)了。
int Max = INT_MIN, Min = INT_MAX;
for(int i = 0; i < n; ++i){
if(A[i] > Max) Max = A[i];
if(A[i] < Min) Min = A[i];
}
vector<int> record(Max-Min+1, 0);
for(int i = 0; i < n; ++i)
record[A[i]-Min] = 1;
int i = 0, j = 1, MAX_DIFF = INT_MIN;
while(j <= Max-Min){
if(record[j] && record[i]){
if(j - i > MAX_DIFF) MAX_DIFF = j - i;
++i; ++j;
}
else{
if(record[j]==0) ++j;
if(record[i]==0) ++i;
}
}
return MAX_DIFF;
}
};
发表于 2017-07-03 16:54:38
回复(0)
int findMaxDivision(vector<int> A, int n) {
// write code here
int bucket[65535] = { 0 };
for (int i = 0; i<n; i++){
bucket[A[i]] = A[i];
}
int del = 0;
int pre = 0;
for (int i = 0; i<65535; i++){
if (bucket[i] - pre>del && pre!=0)
del = bucket[i] - pre;
if (bucket[i]>pre)
pre = bucket[i];
}
return del;
}
发表于 2016-03-26 10:08:33
回复(4)
intfindMaxDivision(vector<int> A, intn) {// write code hereinta[65535]={0};intmin = A[0], max = 0;for(inti = 0; i < A.size(); i++){a[A[i]] = 1;if(min>A[i])min = A[i];if(max<A[i])max = A[i];}intpre = min, maxv = 0;for(inti = min+1; i <= max; i++){if(a[i]==1){intv = i - pre;pre = i;if(maxv<v)maxv = v;}}returnmaxv;}
发表于 2015-09-23 17:47:29
回复(4)
class MaxDivision:
def findMaxDivision( self,a, n):
c=[]
m=[]
if len(a)<2 or len(a)>500:
print ('无效')
else:
b=sorted(a)
for i in range(len(b)):
c.append(b[-len(b)+1+i])
c[-1]=b[-1]
for i in range(len(b)):
m.append(c[i]-b[i])
return max(m)
发表于 2017-04-20 10:19:53
回复(0)
import java.util.*;
public class MaxDivision {
public int findMaxDivision(int[] A, int n) {
// 计数排序,时间复杂度O(max-min+1),空间复杂度O(max-min+1),达不到O(n)
int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
for (int i = 0; i < A.length; i ++) {
max = max > A[i] ? max : A[i];
min = min < A[i] ? min : A[i];
}
boolean[] flag = new boolean[max - min + 1];
for (int i = 0; i < n; i ++) {
flag[A[i] - min] = true;
}
int res = Integer.MIN_VALUE;
int cur = 0, pre = 0;
while ( ! flag[pre]) {
cur ++;
pre ++;
}
for (; cur < flag.length; cur ++) {
if(flag[cur]) {
res = res > cur - pre ? res : cur - pre;
pre = cur;
}
}
return res;
}
}
编辑于 2017-03-11 00:09:32
回复(0)
int findMaxDivision(vector<int> A, int n) {
// write code here
int i = 0;
int max = 0;
int min = 0;
int num = 0;
int maxdiff = 0;
int first = 0;
max = A[0];
min = A[0];
for(i = 0; i<n; i++){
if(max<A[i]){
max = A[i];
}
if(min>A[i]){
min = A[i];
}
}
num = max - min;
vector<int> temp(num+1);
for(i = 0; i < num+1; i++){
temp[i] = -1;
}
for(i = 0; i<n; i++){
temp[A[i]-min] = A[i];
}
first = min;
for(i = 0; i<num+1; i++){
if(temp[i] >= min){
if(maxdiff < (temp[i] - first)){
maxdiff = temp[i] - first;
}
first = temp[i];
}
}
return maxdiff;
}
发表于 2016-12-08 21:00:24
回复(0)
import java.util.*;
public class MaxDivision {
private static int min =0;
private static int max=0;
public int findMaxDivision(int[] A, int n) {
// write code here
int index[] = getM(A, n);
for(int i=0; i<n; i++){
index[A[i]-min] = 1;
}
int rst = 0;
for(int i=0; i<max-min+1; i++){
int j = i;
while(j<max-min+1&&index[j]==0){
j++;
}
if(rst<j-i){
rst = j-i;
}
i=j;
}
return rst+1;
}
public static int[] getM(int[] a,int n){
max = a[0];
min = a[0];
for(int i=1; i<n; i++){
if(max<a[i]){
max=a[i];
}
if(min>a[i]){
min=a[i];
}
}
return new int[max-min+1];
}
}
发表于 2016-08-22 15:22:49
回复(0)
int findMaxDivision(vector<int> A, int n)
{
// write code here
int arry[65535];
memset(arry,-1,65535);
int maxnum = 0;
for(int i = 0; i < n; i++)
{
arry[A.at(i)] = A.at(i);
if(A.at(i) > maxnum)
maxnum = A.at(i);
}
int j = 0;
int s=0;
int maxResult = 0;
while(arry[j] == -1)
j++;
s = j;
while (j<=maxnum)
{
if(arry[j] != -1)
{
if(maxResult < (arry[j] - arry[s]))
maxResult = arry[j] - arry[s];
s = j;
}
j++;
}
return maxResult;
}
发表于 2016-04-28 20:15:12
回复(0)
最近看了计数排序。感觉做这个题傻傻的{499,200}让我觉得自己好***
import java.util.*;
public class MaxDivision {import java.util.*;
public int findMaxDivision(int[] A, int n) {
// write code here
int []C = new int[n];
//确定计数数组长度
int max = 0;
for(int i =0;i<n;i++){
if(A[i]>max)
max = A[i];
}
//计数数组
int[]B = new int[max+1];
for(int i = 0;i<n;i++){
B[A[i]]++;
}
//计数叠加
for(int i =1;i<max+1;i++){
B[i] = B[i-1]+B[i];
}
//根据计数决定位置
for(int i = n-1;i>=0;i--){
C[B[A[i]]-1] = A[i];
B[A[i]]--;
}
//选最大值
int Md = 0;
for(int i = 1;i<n;i++){
if(C[i]-C[i-1]>Md){
Md = C[i]-C[i-1];
}
}
return Md;
}
}
发表于 2016-04-19 22:28:16
回复(1)
public int findMaxDivision(int[] A, int n) {
// write code here
int maxOfinput=628,maxD=0,index=0,i=0,b[]=new int[maxOfinput];
while(i<n) b[A[i++]]=1;i=0;
while(i<maxOfinput&&b[i]==0)i++;index=i++;
while(i<maxOfinput){
while(i<maxOfinput&&b[i]==0)i++;
if(i<maxOfinput) maxD=i-index>maxD?i-index:maxD;index=i++;
}
return maxD;
}
编辑于 2016-03-29 23:48:32
回复(0)
按着老师的代码扒了一遍。。什么都没动就是加了点备注
public int getTwoNumPoorMax2(int arr[],int l){
//数组长度小于2不需要进行处理
if(l<2){
return 0;
}
/**
* 最大结果差值
*/
int maxPoo=0;
/**
* 数组中最大值
*/
int min=arr[0];
/**
* 数组中最小值
*/
int max=arr[0];
//去除数组中的最大值和最小值
for(int i=0;i<l;i++){
min = Math.min(min, arr[i]);
max = Math.max(max, arr[i]);
}
//最大值等于最小值则返回0
if(min==max){
return 0;
}
// 定义三个n+1长度的数组
/**
* 单个桶中最小值 最小值桶
*/
int mingroup[]=new int[l+1];
/**
* 单个桶中最大值 最大值桶
*/
int maxgroup[]=new int[l+1];
/**
* 桶是否为空桶
*/
boolean judgeNoEmpty[] = new boolean[l+1];
//遍历
for(int i=0;i<l;i++){
//判定当前值所在的桶
int index = countArrIndex(arr[i], min, max, l);
//判定是否已经在当前桶中放入过数据
if(judgeNoEmpty[index]){
//放入过数据则做对比
//当前值比之前最小值桶中值小，则替换之前值，否则不替换
mingroup[index] = Math.min(mingroup[index],arr[i]);
//当前值比之前最大值桶中值大，则替换之前值，否则不替换
maxgroup[index] = Math.max(maxgroup[index], arr[i]);
}else{
//给未曾放入过值的桶放入初始值
mingroup[index] = arr[i];
maxgroup[index] = arr[i];
judgeNoEmpty[index] = true;
}
}
//遍历使用的位置值变量
int i=0;
//记录桶中最大值
int lastmax = 0;
for(;i<=l;i++){
if(judgeNoEmpty[i]){//找到第一个不为null的桶
lastmax = maxgroup[i];//取当前不为空桶中的最大值
break;
}
}
//进行余下桶值的对比
for(;i<=l;i++){
if(judgeNoEmpty[i]){
maxPoo = Math.max(maxPoo, mingroup[i]-lastmax);
lastmax = maxgroup[i];
}
}
return maxPoo;
}
/**
* 计算当前传入值应该在总体桶的哪个位置
* @param num
* @param min
* @param max
* @param length
* @return
*/
public int countArrIndex(int num,int min,int max,int length){
//通过当前值和最大最小值间的关系可以计算出当前数值所在的桶的索引位置
return (num-min)*length/(max-min);
}
发表于 2015-09-17 15:10:25
回复(0)
桶排序的思想：
找最大值和最小值。分配(max-min+1)个桶，一定存在空桶。(空桶可能存在多个)
最大差值在空桶附近的两个桶之间。
C++代码如下：
if(n <= 0) return 0;
int mx = A[0], mn = A[0];
for(auto v : A){//找最大最小值
if(mx < v) mx = v;
if(mn > v) mn = v;
}
vector<int> range(mx - mn + 1, 0);//max-min+1个桶
int mxinterval = 0, pre = mn, curinterval = 0;
for(auto v : A){
++range[v - mn];//为每个数分配相应的桶
}
for(int v = mn + 1; v <= mx; ++v){
if (range[v - mn] != 0){//桶非空
curinterval = v - pre;
pre = v;//前一个非空的桶内的数
if (mxinterval < curinterval){
mxinterval = curinterval;
}
}
}
return mxinterval;
编辑于 2016-05-01 14:30:48
回复(3)
参照前面一位同学的思路 本题不应该直接使用Arrays的sort方法
我们先看一下Arrays.sort的底层实现
是一个双重循环，这样的话复杂度是达不到题目所要求的O(n)，故不能直接调用sort这个API方法
最适合的方法是桶排序：
1.找出最大值和最小值。
2.生成一个最大值-最小值的区间 比如最大值9，最小值3，那就需要7个桶
3.往里面填
4.查找空桶，最多的即为最大差值。
public static int findMaxDivision(int[] A, int n) {
int maxnum = A[0];
int minnum = A[0];
for (int i = 0; i < A.length; i++) {
if (maxnum < A[i])
maxnum = A[i];
if (minnum > A[i])
minnum = A[i];
}
int[] arr = new int[maxnum - minnum + 1]; // 生成桶
for (int i = 0; i < A.length; i++) {
arr[A[i] - minnum]++; // 填桶
}
int count = 0;
int max = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) { // 桶为空
count++; //记录连续空桶数
} else {
if (max < count)
max = count;
count = 0;
}
}
return max+1; //如最大值为9，最小值为3，中间有5个空桶，但差值应为6
}
编辑于 2016-06-23 20:28:23
回复(22)
问题信息
通过挑战的用户
查看代码-
2022-11-10 16:32:26 -
2022-09-20 17:12:55 -
2022-09-14 11:12:01
-
2022-09-02 12:57:00 -
2022-08-27 18:53:19
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
