不基于比较的排序找到数组排序后的最大差值

题目描述

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且要求不能用非基于比较的排序

注意不基于比较哦

思路

思路：桶排序

假设数组长度为n，准备n+1个桶
遍历该数组，将最小值放入到第1个位置，将最大值放入到最后一个位置
将剩下的数等分成等分成n-1份依次放入剩下对应范围的桶中，
最后这n+1个桶中至少有一个空桶，说明桶内的数值差不是最大差值，我们去桶间找最大差值
对于每个桶，我们都保存了每个桶的最小值和最大值，从第2个桶开始，每次计算当前桶的最小值与前一个桶(要有元素)的最大值的差，过程中我们动态更新最大差值

具体编码

实现代码


func GetMaxDiff(nums []int) int {
	maxNum := make([]int, len(nums)+1)
	minNum := make([]int, len(nums)+1)
	hasNum := make([]bool, len(nums)+1)      //用来标记桶是否有值
	min, max := math.MaxInt64, math.MinInt64 //整个数组的最小值和最大值
	maxDiff := math.MinInt64                 //最大差值

	//找数组的最大值与最小值
	for _, v := range nums {
		if v > max {
			max = v
		}
		if min > v {
			min = v
		}
	}

	//第一个位置放最小值，第2个位置放最大值
	hasNum[0], hasNum[len(nums)] = true, true
	//将最大值与最小值之间等分成n(n为数组的长度)-1份，依次遍历属于哪个范围就加入哪个桶
	diff := float64(max-min) / float64(len(nums)-1)
	for _, v := range nums {
		indexBucket := int(math.Ceil(float64(v-min) / diff))
		//如果当前桶没有值
		if !hasNum[indexBucket] {
			maxNum[indexBucket] = v
			minNum[indexBucket] = v
		} else {
			//当前桶有值且当前桶的最大值小于当前元素 则更新
			if maxNum[indexBucket] < v {
				maxNum[indexBucket] = v
			}
			if minNum[indexBucket] > v {
				minNum[indexBucket] = v
			}
		}
		//最后将当前桶置为true，说明已放入元素
		hasNum[indexBucket] = true
	}

	//这里要注意：不是两个相邻的桶之间进行比较
	//遍历桶，找当前桶与上一个存放元素的桶的最大差值并返回
	lastMax := min //存放上一个最大
	for i := 1; i < len(nums); i++ {
		if hasNum[i] {
			if maxDiff < minNum[i]-lastMax {
				maxDiff = minNum[i] - lastMax
			}
			lastMax = maxNum[i]
		}

	}
	return maxDiff
}

func main() {
	nums := utils.RandArrayRange(10, 10, 99)
	fmt.Println(nums)
	fmt.Println(GetMaxDiff(nums))
}