Demo entry 6566054

1

   

Submitted by anonymous on Jun 03, 2017 at 02:27
Language: Java. Code size: 757 Bytes.

/*
 * 利用桶排序的思想 首先找到最大值 最小值 然后对数据范围建立一个桶 桶的个数是max-min+1 这样所有数据都放在桶里 肯定会有空的
 * 空的个数就是 相邻的最大差值啦 牺牲空间换时间的算法
 * 
 */
public int findMaxDivision(int[] A, int n) {
	int max = A[0];
	int min = A[0];
	for (int i = 0; i < n; i++) { // 找打最大值最小值
		if (A[i] > max) {
			max = A[i];
		}
		if (A[i] < min) {
			min = A[i];
		}
	}

	int[] arr = new int[max - min + 1]; // 定义桶 个数为max-min+1;

	for (int i = 0; i < n; i++) {// 填桶
		arr[A[i] - min]++; // 这个位置值加1
	}

	// 查看空桶的个数
	int count = 0;
	int maxCount = 0;
	for (int i = 0; i < arr.length; i++) {
		if (arr[i] == 0) {// 空桶
			count++; // 连续空桶的个数
		} else {
			if (maxCount < count) {
				maxCount = count;
			}
			count = 0;
		}
	}

	return maxCount + 1; // 两个数据中间隔了3个空桶 最大间隔就是4
}

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).