欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

给定一个数组,如果排序后,求相邻两个数的最大差值,要求时间复杂度为n,不能使用非基于比较的排序

程序员文章站 2024-03-15 22:38:48
...

问题:
给定一个数组,如果排序后,求相邻两个数的最大差值,要求时间复杂度为n,不能使用非基于比较的排序
分析:
①使用桶的思想,设置N+1个桶,根据鸽笼原理,必然有一个空桶,那么就排除了最大差值在一个桶内,因为空桶两侧的差距肯定大于桶内的差距

②但,最大差值不见得是空桶左侧max和空桶右侧min,需要依次遍历求差值

③使用桶的思想时间复杂度是N,但没有使用桶排序,桶排序是非基于比较的排序,桶就是容器的含义,计数排序和基数排序是桶排序的具体实现,是稳定的排序,时间复杂度为N

牛客-基础3-1:18:00

public static int maxGap(int[] nums) {
		if (nums == null || nums.length < 2) {
			return 0;
		}
		int len = nums.length;
		int min = Integer.MAX_VALUE;//最小值是系统最大值
		int max = Integer.MIN_VALUE;//最大值是系统最小值
		for (int i = 0; i < len; i++) {
			min = Math.min(min, nums[i]);
			max = Math.max(max, nums[i]);
		}
		if (min == max) {
			return 0;
		}
		//下面三个数组就构成了桶,桶存储是是否为空、最大值、最小值
		boolean[] hasNum = new boolean[len + 1];
		int[] maxs = new int[len + 1];//划分成N+1个桶
		int[] mins = new int[len + 1];
		
		int bid = 0;
		for (int i = 0; i < len; i++) {
			bid = bucket(nums[i], len, min, max);
			mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
			maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
			hasNum[bid] = true;//不是空桶
		}
		//前一个桶的max和后一个桶的min的差值进行比较
		int res = 0;
		int lastMax = maxs[0];
		for (int i=1; i <= len; i++) {
			if (hasNum[i]) {
				res = Math.max(res, mins[i] - lastMax);
				lastMax = maxs[i];
			}
		}
		return res;
	}

	public static int bucket(long num, long len, long min, long max) {
		return (int) ((num - min) * len / (max - min));
		//(num-min)/(max-min)就是占所有的比例
		//返回的结果是第几个桶
	}