各大高校工科男身价排行 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

各大高校工科男身价排行

各大高校工科男身价排行# Joke - 肚皮舞运动

N*82012-03-30 07:03

1 楼

给一个unsorted array，求这个数组中最小的元素差，差的定义为abs(a[i]-a[j])
where i != j .
要求O(n)时间，空间无限，数组没有上下限(既不能用radix/counting sort)。
Ex: input = {5, 13, 7, 0, 10, 20, 1, 15, 4, 18}
output = abs(0-1) = 1
有O(n)算法吗？

G*o2012-03-30 07:03

2 楼

p*22012-03-30 07:03

3 楼

你是为了准备面试呢？还是做着玩呢？

【在 N*****8 的大作中提到】

: 给一个unsorted array，求这个数组中最小的元素差，差的定义为abs(a[i]-a[j])
: where i != j .
: 要求O(n)时间，空间无限，数组没有上下限(既不能用radix/counting sort)。
: Ex: input = {5, 13, 7, 0, 10, 20, 1, 15, 4, 18}
: output = abs(0-1) = 1
: 有O(n)算法吗？

c*k2012-03-30 07:03

4 楼

五道口理工的男生写的吧

【在 G***o 的大作中提到】

N*82012-03-30 07:03

5 楼

当然是面试啊。

【在 p*****2 的大作中提到】

:
: 你是为了准备面试呢？还是做着玩呢？

n*t2012-03-30 07:03

6 楼

我咋觉得是浙大弄的呢？

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

: 五道口理工的男生写的吧

N*82012-03-30 07:03

7 楼

原题在这儿
http://stackoverflow.com/questions/1669922/is-it-possible-to-fi
careercup上面也有人贴过，但是除了radix/counting sort就没有更好的方法了。

t*r2012-03-30 07:03

8 楼

不好意思，拖后腿了。

【在 G***o 的大作中提到】

j*n2012-03-30 07:03

9 楼

只能扫１遍？　你自己先扫１遍不就知道上下线了？

N*82012-03-30 07:03

10 楼

其实更多的是想避免用radix/counting，不然的话先sorting，然后比较相邻的两数求
最小差就比较简单了。

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

: 只能扫１遍？　你自己先扫１遍不就知道上下线了？

f*i2012-03-30 07:03

11 楼

It can be done in O(n) by DP
For a given array Arr do the following
1) an array left_smaller, where left_smaller[i] is A[j] such that A[j]j2) an array right_smaller, where right_smaller[i] is A[j] such that A[j]], j>i, and j-i is min, make it -1 if i is lengthof(Arr)
3) an array left_greater, where left_greater[i] is A[j] such that A[j]>A[i],
j4) an array right_greater, where right_smaller[i] is A[j] such that A[j]>A[i
], j>i, and j-i is min, make it -1 if i is lengthof(Arr)
Such arrays can be created in O(n)
next, find i such that min{left_greater[i]-i, right_greater[i]-i, i-left_
smaller[i], i-right_smaller[i]} is minimum
another O(n)

c*r2012-03-30 07:03

12 楼

为什么不是 5-4 =1，非要是1-0 =1？

【在 N*****8 的大作中提到】

e*x2012-03-30 07:03

13 楼

],
[i
],
[i
how to create such arrays in O(n)?

【在 f*********i 的大作中提到】

: It can be done in O(n) by DP
: For a given array Arr do the following
: 1) an array left_smaller, where left_smaller[i] is A[j] such that A[j]: j: 2) an array right_smaller, where right_smaller[i] is A[j] such that A[j]: ], j>i, and j-i is min, make it -1 if i is lengthof(Arr)
: 3) an array left_greater, where left_greater[i] is A[j] such that A[j]>A[i],
: j: 4) an array right_greater, where right_smaller[i] is A[j] such that A[j]>A[i
: ], j>i, and j-i is min, make it -1 if i is lengthof(Arr)

c*r2012-03-30 07:03

14 楼

贴一个，大家看看对不对:
//do not deal with array with size less than 2
int findMinDiff(int A[], int n)
{
if (n <2)
{
return -1;
}
int minElem = A[0];
int minDiff = abs(A[1] -A[0]);
for (int i = 1; i < n; ++i)
{
if (abs(A[i] - minElem) < minDiff)
{
minDiff = abs(A[i] - minElem);
}
if (A[i] < minElem)
{
minElem = A[i];
}
}
return minDiff;
}

p*22012-03-30 07:03

15 楼

感觉不对。

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

: 贴一个，大家看看对不对:
: //do not deal with array with size less than 2
: int findMinDiff(int A[], int n)
: {
: if (n <2)
: {
: return -1;
: }
: int minElem = A[0];
: int minDiff = abs(A[1] -A[0]);

c*r2012-03-30 07:03

16 楼

果然是不对的：）
如果数组里有负数，就是错的....（可能还有很多其他情况都不对，没仔细想）
比如：A[] = {5,-1,5,0,10,20,1,15,4,18}，返回1，应该返回0.
看来O（n）解法没那么简单....

【在 p*****2 的大作中提到】

:
: 感觉不对。

z*52012-03-30 07:03

17 楼

空间不限的话就好办了，建一个足够大的数组A（或者查一遍给定的数组，看最大多大
），A中元素全为0，用你给的数组里面的元素做A的index，遍历一遍给定的数组，把存
在的元素对应的A中的位置的元素变成1。然后只要查一遍A里面最小的连续的0是多少
个就好了。这是3n的复杂度，应该也算是O（n）了吧…… 不知道对不对

p*22012-03-30 07:03

18 楼

这么怎么会是3n？

【在 z********5 的大作中提到】

: 空间不限的话就好办了，建一个足够大的数组A（或者查一遍给定的数组，看最大多大
: ），A中元素全为0，用你给的数组里面的元素做A的index，遍历一遍给定的数组，把存
: 在的元素对应的A中的位置的元素变成1。然后只要查一遍A里面最小的连续的0是多少
: 个就好了。这是3n的复杂度，应该也算是O（n）了吧…… 不知道对不对

c*r2012-03-30 07:03

19 楼

看不太明白，可否写个程序？

【在 z********5 的大作中提到】

z*52012-03-30 07:03

20 楼

哎呀，脑子进水了，错了错了，请忽略我的回答……

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

: 看不太明白，可否写个程序？