# Leetcode 164 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

Suppose there are N elements and they range from A to B. Then the maximum gap will be no smaller than ceiling[(B - A) / (N - 1)] Let the length of a bucket to be len = ceiling[(B - A) / (N - 1)], then we will have at most num = (B - A) / len + 1 of bucket

```class Solution {
public:
int maximumGap(vector<int>& nums) {
if(nums.size()<2) return 0;
int minn = INT_MAX;
int maxx = INT_MIN;
for(int i = 0; i<nums.size(); i++)
{
minn = min(minn, nums[i]);
maxx = max(maxx, nums[i]);
}
double len = (maxx - minn)*1.0 / (nums.size() - 1);
if(len == 0) return 0;//防止所有元素一样大
int cnt = floor((maxx - minn) / len + 1);
vector<int> minb(cnt, INT_MAX);
vector<int> maxb(cnt, INT_MIN);
for(int i = 0;i<nums.size();i++) //元素分入桶
{
int id = floor((nums[i] - minn) / len);
minb[id] = min(minb[id], nums[i]);
maxb[id] = max(maxb[id], nums[i]);
}
int res = 0, premax = maxb[0];//第一个桶包含最小值，因此一定不为空
for(int i = 1;i<cnt; i++)
{
if(minb[i] != INT_MAX)
{
res = max(res, minb[i] - premax);
premax = maxb[i];
}
}
return res;
}
};```

0 条评论

## 相关文章

### 2729:Blah数集

2729:Blah数集 查看 提交 统计 提问 总时间限制:3000ms内存限制:65536kB描述大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对...

3084

3384

### Scala Macros － 元编程 Metaprogramming with Def Macros

Scala Macros对scala函数库编程人员来说是一项不可或缺的编程工具，可以通过它来解决一些用普通编程或者类层次编程（type level pr...

2919

2425

2234

### Gym 100952J&&2015 HIAST Collegiate Programming Contest J. Polygons Intersection【计算几何求解两个凸多边形的相交面积板子题

J. Polygons Intersection time limit per test：2 seconds memory limit per test：64 ...

2757

1.3K9

891

3026

### C/C++——柔性数组

1、问题来源 在博文数据结构和算法——kd树中，在构建kd树的过程中，有如下的一段代码： #define MAX_LEN 1024 typedef struc...

2994