N*****8
发帖数: 253 | 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)算法吗？ | p*****2
发帖数: 21240 | 2
你是为了准备面试呢？还是做着玩呢？
【在 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)算法吗？
| N*****8
发帖数: 253 | 3 当然是面试啊。
【在 p*****2 的大作中提到】
:
: 你是为了准备面试呢？还是做着玩呢？
| N*****8
发帖数: 253 | | j*****n
发帖数: 1545 | | N*****8
发帖数: 253 | 6 其实更多的是想避免用radix/counting，不然的话先sorting，然后比较相邻的两数求
最小差就比较简单了。
【在 j*****n 的大作中提到】
: 只能扫１遍？ 你自己先扫１遍不就知道上下线了？
| f*********i
发帖数: 197 | 7 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)
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*******r
发帖数: 610 | 8 为什么 不是 5-4 =1， 非要是1-0 =1？
【在 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)算法吗？
| e******x
发帖数: 184 | 9
],
[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*******r
发帖数: 610 | 10 贴一个，大家看看对不对:
//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*****2
发帖数: 21240 | 11
感觉不对。
【在 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*******r
发帖数: 610 | 12 果然是不对的：）
如果数组里有负数，就是错的....（可能还有很多其他情况都不对，没仔细想）
比如：A[] = {5,-1,5,0,10,20,1,15,4,18}， 返回1，应该返回0.
看来O（n）解法没那么简单....
【在 p*****2 的大作中提到】
:
: 感觉不对。
| z********5
发帖数: 176 | 13 空间不限的话就好办了，建一个足够大的数组A（或者查一遍给定的数组，看最大多大
），A中元素全为0，用你给的数组里面的元素做A的index，遍历一遍给定的数组，把存
在的元素对应的A中的位置的元素变成1。 然后只要查一遍A里面最小的连续的0是多少
个就好了。 这是3n的复杂度，应该也算是O（n）了吧…… 不知道对不对 | p*****2
发帖数: 21240 | 14
这么怎么会是3n？
【在 z********5 的大作中提到】
: 空间不限的话就好办了，建一个足够大的数组A（或者查一遍给定的数组，看最大多大
: ），A中元素全为0，用你给的数组里面的元素做A的index，遍历一遍给定的数组，把存
: 在的元素对应的A中的位置的元素变成1。 然后只要查一遍A里面最小的连续的0是多少
: 个就好了。 这是3n的复杂度，应该也算是O（n）了吧…… 不知道对不对
| c*******r
发帖数: 610 | 15 看不太明白，可否写个程序？
【在 z********5 的大作中提到】
: 空间不限的话就好办了，建一个足够大的数组A（或者查一遍给定的数组，看最大多大
: ），A中元素全为0，用你给的数组里面的元素做A的index，遍历一遍给定的数组，把存
: 在的元素对应的A中的位置的元素变成1。 然后只要查一遍A里面最小的连续的0是多少
: 个就好了。 这是3n的复杂度，应该也算是O（n）了吧…… 不知道对不对
| z********5
发帖数: 176 | 16 哎呀， 脑子进水了，错了错了，请忽略我的回答……
【在 c*******r 的大作中提到】
: 看不太明白，可否写个程序？
|
|
