y*****e
发帖数: 712 | 1 Given an unsorted array, find the maximum difference between the successive
elements in its sorted form.
Try to solve it in linear time/space.
我理解的是是找相邻两个数的差，把这些差（gap)从小到大排列，
但最后只return最大的差就行了？那还排列大小干嘛？
能有人给个例子介绍一下吗？
谢谢！ |
m*********1
发帖数: 204 | 2 我的理解是不是，例如
3 5 6 10 7 11 7 8
那么里面最大的连续数列是5 6 7 8 所以 就是8-5 = 3 |
y*****e
发帖数: 712 | 3 啊，原来是这样，那不就是longest consecutive sequence的变形题吗，
有其他的考点吗？
【在 m*********1 的大作中提到】
: 我的理解是不是，例如
: 3 5 6 10 7 11 7 8
: 那么里面最大的连续数列是5 6 7 8 所以 就是8-5 = 3
|
h*********2
发帖数: 444 | 4 这个题的意思是找最大的排序后相邻的两个数之间的gap
比如 3 5 1 2 9
排序后是 1 2 3 5 9
那么最大的gap就是9-5 = 4 |
w****a
发帖数: 710 | 5 bucket sorting的变种。
至少LC给出的solution是这个意思。
【在 y*****e 的大作中提到】
: 啊，原来是这样，那不就是longest consecutive sequence的变形题吗，
: 有其他的考点吗？
|
s***c
发帖数: 639 | 6 最大是指在，如果输入数组排序后的新数组
写了一个，是O(n)，但过不了大数集，需要优化
class Solution {
public:
int maximumGap(vector &num) {
if(num.size()<2) return 0;
if(num.size()==2) return abs(num[0]-num[1]);
unordered_set hh;
int res(0), val_pre(-1), val_cur(-1);
int vmax(-1), vmin(INT_MAX);
for(int i=0; i
hh.insert(num[i]);
vmax=std::max(vmax, num[i]);
vmin=std::min(vmin, num[i]);
}
for(int val=vmin; val
if(hh.find(val)!=hh.end()){
if(val_pre<0) val_pre = val;
val_cur = val;
res = std::max(res, val_cur-val_pre);
val_pre = val_cur;
}
}
res=std::max(res, vmax-val_pre);
return res;
}
};
successive
【在 y*****e 的大作中提到】
: Given an unsorted array, find the maximum difference between the successive
: elements in its sorted form.
: Try to solve it in linear time/space.
: 我理解的是是找相邻两个数的差，把这些差（gap)从小到大排列，
: 但最后只return最大的差就行了？那还排列大小干嘛？
: 能有人给个例子介绍一下吗？
: 谢谢！
|
d****n
发帖数: 233 | 7 我也是看discussion受到启发，先找max和min， 再把max-min分成n个区间。把原数组
映射到这n个区间，对映射到每个区间的数，找最大和最小。 在从1到n找这些区间的最
大距离。
解法在我的blog： http://codeanytime.blogspot.com/2014/12/maximum-gap.html
【在 s***c 的大作中提到】
: 最大是指在，如果输入数组排序后的新数组
: 写了一个，是O(n)，但过不了大数集，需要优化
: class Solution {
: public:
: int maximumGap(vector &num) {
: if(num.size()<2) return 0;
: if(num.size()==2) return abs(num[0]-num[1]);
: unordered_set hh;
: int res(0), val_pre(-1), val_cur(-1);
: int vmax(-1), vmin(INT_MAX);
|
s***c
发帖数: 639 | 8 得把bucket变大，这下可以过了
class Solution {
public:
int maximumGap(vector &num) {
unordered_set hh;
int res(0);
int vmax(-1), vmin(INT_MAX);
for(int i=0; i
hh.insert(num[i]);
vmax=std::max(vmax, num[i]);
vmin=std::min(vmin, num[i]);
}
int hsz=hh.size();
if(hsz<=1) return res;
double dbin = double(vmax-vmin)/(hsz-1);
vector minvec(hsz, INT_MAX), maxvec(hsz, -1);
for(int i=0; i
int val=num[i], ib=(int)((val-vmin)/dbin);
minvec[ib] = std::min(minvec[ib], val);
maxvec[ib] = std::max(maxvec[ib], val);
}
int maxpre(-1);
for(int i=0; i
if(maxvec[i]<0) continue;
if(maxpre<=0) maxpre=maxvec[i];
res = std::max(res, minvec[i]-maxpre);
maxpre = maxvec[i];
}
return res;
}
};
【在 s***c 的大作中提到】
: 最大是指在，如果输入数组排序后的新数组
: 写了一个，是O(n)，但过不了大数集，需要优化
: class Solution {
: public:
: int maximumGap(vector &num) {
: if(num.size()<2) return 0;
: if(num.size()==2) return abs(num[0]-num[1]);
: unordered_set hh;
: int res(0), val_pre(-1), val_cur(-1);
: int vmax(-1), vmin(INT_MAX);
|
s***c
发帖数: 639 | 9 真得把bucket变大，加上一定只能遍历数组才行呀
【在 d****n 的大作中提到】
: 我也是看discussion受到启发，先找max和min， 再把max-min分成n个区间。把原数组
: 映射到这n个区间，对映射到每个区间的数，找最大和最小。 在从1到n找这些区间的最
: 大距离。
: 解法在我的blog： http://codeanytime.blogspot.com/2014/12/maximum-gap.html
|
y*****e
发帖数: 712 | 10 非常感谢ls的几位提供思路，写了一个Java的，过了OJ, oh yeah!! |
