Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

桶排序

复杂度

O(N) 时间 O(N) 空间

思路

假设有N个元素A到B。

那么最大差值一定大于floor[(B - A) / (N - 1)]，floor就是向下取整

令bucket（桶）的大小len = floor[(B - A) / (N - 1)]，则最多会有(B - A) / len + 1个桶

对于数组中的任意整数K，很容易通过算式loc = (K - A) / len找出其桶的位置，然后维护每一个桶的最大值和最小值

由于同一个桶内的元素之间的差值至多为len - 1，因此最终答案不会从同一个桶中选择。

对于每一个非空的桶p，找出下一个非空的桶q，则q.min - p.max可能就是备选答案。返回所有这些可能值中的最大值。

注意

注意特殊情况

代码

主程序：

public int maximumGap(int[] nums) {
int n = nums.length;
if (n
Utilities:

public int getMax(int[] nums) {
int max = Integer.MIN_VALUE;
for (int cur : nums)
max = Math.max(cur, max);
return max;
}

public int getMin(int[] nums) {
int min = Integer.MAX_VALUE;
for (int cur : nums)
min = Math.min(cur, min);
return min;
}

public int find(Bucket[] buckets) {
int premax = Integer.MIN_VALUE;
int curmin = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i
Bucket类:

class Bucket {
int left;//inclusive，其实这个是没必要的
int right;//inclusive，其实这个是没必要的
int max;
int min;
Bucket(int left, int right) {
this.left = left;
this.right = right;
this.max = Integer.MIN_VALUE;
this.min = Integer.MAX_VALUE;
}
}

关键字：leetcode, int, buckets, min

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！