求解释丽寇儿的新题maximum gap题目到底啥意思？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求解释丽寇儿的新题maximum gap题目到底啥意思？

求解释丽寇儿的新题maximum gap题目到底啥意思？# JobHunting - 待字闺中

y*e2014-12-14 08:12

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*12014-12-14 08:12

2 楼

我的理解是不是，例如
3 5 6 10 7 11 7 8
那么里面最大的连续数列是5 6 7 8 所以就是8-5 = 3

y*e2014-12-14 08:12

3 楼

啊，原来是这样，那不就是longest consecutive sequence的变形题吗，
有其他的考点吗？

【在 m*********1 的大作中提到】

: 我的理解是不是，例如
: 3 5 6 10 7 11 7 8
: 那么里面最大的连续数列是5 6 7 8 所以就是8-5 = 3

h*22014-12-14 08:12

4 楼

这个题的意思是找最大的排序后相邻的两个数之间的gap
比如 3 5 1 2 9
排序后是 1 2 3 5 9
那么最大的gap就是9-5 = 4

w*a2014-12-14 08:12

5 楼

bucket sorting的变种。
至少LC给出的solution是这个意思。

【在 y*****e 的大作中提到】

: 啊，原来是这样，那不就是longest consecutive sequence的变形题吗，
: 有其他的考点吗？

s*c2014-12-14 08:12

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; ihh.insert(num[i]);
vmax=std::max(vmax, num[i]);
vmin=std::min(vmin, num[i]);
}

for(int val=vmin; valif(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*n2014-12-14 08:12

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*c2014-12-14 08:12

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; ihh.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; iint 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; iif(maxvec[i]<0) continue;
if(maxpre<=0) maxpre=maxvec[i];
res = std::max(res, minvec[i]-maxpre);
maxpre = maxvec[i];
}

return res;
}
};

【在 s***c 的大作中提到】

s*c2014-12-14 08:12

9 楼

真得把bucket变大，加上一定只能遍历数组才行呀

【在 d****n 的大作中提到】

: 我也是看discussion受到启发，先找max和min，再把max-min分成n个区间。把原数组
: 映射到这n个区间，对映射到每个区间的数，找最大和最小。在从1到n找这些区间的最
: 大距离。
: 解法在我的blog： http://codeanytime.blogspot.com/2014/12/maximum-gap.html

y*e2014-12-14 08:12

10 楼

非常感谢ls的几位提供思路，写了一个Java的，过了OJ, oh yeah!!