題目:計(jì)算數(shù)組中相鄰數(shù)據(jù)的最大差值
要求時(shí)間復(fù)雜度為 O(N)
算法思想:
利用桶的思想
- 1.假設(shè)數(shù)組長度為N,那么我們做N+1個(gè)桶,即可以完全放下數(shù)組
- 2.首先我們求出數(shù)組中的最大值和最小值,利用這個(gè)可對(duì)數(shù)組中數(shù)據(jù)分桶
- 3.將數(shù)組中的數(shù)據(jù)放入桶中,桶中只保留插入的最大值和最小值
- 4.
關(guān)于紅字部分解讀圖:
算法代碼部分
package com.day1.practice;
public class MyMaxGap { //找出數(shù)組中相鄰兩個(gè)數(shù)的最大差值,要求時(shí)間復(fù)雜度為(N)
public static int maxGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int max=Integer.MIN_VALUE;
int min=Integer.MAX_VALUE;
int len=nums.length;
for(int i=0;i<len;i++){ //找出最大值最小值
if (nums[i]>max)
max=nums[i];
if (nums[i]<min)
min=nums[i];
}
//分三個(gè)桶隊(duì)列
boolean[] hasNum = new boolean[len + 1]; //存放每個(gè)桶是否為空的判斷
int[] maxs = new int[len + 1];//存放每個(gè)桶里的最大值
int[] mins = new int[len + 1];//存放每個(gè)桶里的最小值
int bid;//判斷i上的值在桶中的位置
for(int i=0;i<len;i++){//遍歷數(shù)組.將數(shù)組中每個(gè)數(shù)組與對(duì)應(yīng)桶中位置上的數(shù)據(jù)比對(duì),更新桶中最大值或最小值
bid = bucket(nums[i], len, min, max);
maxs[bid]=hasNum[bid]?Math.max(maxs[bid],nums[i]):nums[i];
mins[bid]=hasNum[bid]?Math.max(maxs[bid],nums[i]):nums[i];
hasNum[bid]=true;
}
int res = Integer.MIN_VALUE;
int lastMax = maxs[0];
int i = 1;
for(;i<len+1;i++){
if (hasNum[i]){//如果桶里有數(shù)據(jù),就用當(dāng)前桶最小值和前一個(gè)桶最大值相減,結(jié)果再和res相比
res=Math.max(mins[i]-lastMax,res);
lastMax=maxs[i];
}
}
return res;
}
public static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}
//test
public static void main(String[] args){
int[] arrs=new int[]{2,5,8,9,4,22,44,23,21};
int res=maxGap(arrs);
System.out.println(res);
}
}
