r***8 发帖数: 86 | 1 给 N个排好序的正整数一维序列(可看成N个一维数组)
ASSUME 最长序列为 长度为L,最短为S S>=1
这些所有正整数没有重复的数
现要求从每一个序列中只取一个数组成一个新的N长度序列
怎么取才能使新序列中,最大数与最小数的差为最小
给出最佳算法,复杂度是多少。 |
p********7 发帖数: 549 | 2 这个题和在文章里面找n个不同words的最小距离很像。算法是每个数组分配一个指针,
然后取每个指针指向的数组头一个数,排序获得mindistance,每次把最小的数取出,
换为它所在数组的下一个数,更新排序,更新mindistance。复杂度是 总长度*logN |
A*********r 发帖数: 564 | 3 版权是啥意思? 你想出来的题,还是是你有独特解法的题?
这道题让我想起了那个N个数中取出K个数作为子集,使得子集的半径最小的题,可能更
复杂一些。。
可以用DP, 令 F(k,i,j)表示从前i个序列中取出k的数的最小差值,其中i个序列中取第
j个数:
F(k,i,j)= min {x in 序列 i-1 } { F(k-1,i-1,x)+abs(A[i-1][x]-A[i][j]) }
算法复杂度为O(N^2*L), 可以优化为 O(N^2*logL),其中L为最长序列的长度。。
【在 r***8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给 N个排好序的正整数一维序列(可看成N个一维数组) : ASSUME 最长序列为 长度为L,最短为S S>=1 : 这些所有正整数没有重复的数 : 现要求从每一个序列中只取一个数组成一个新的N长度序列 : 怎么取才能使新序列中,最大数与最小数的差为最小 : 给出最佳算法,复杂度是多少。
|
A*********r 发帖数: 564 | 4 解法很简洁,有点greedy的意思。
时间复杂度有点困惑,貌似应该是 总元素个数*NlogN :每一次只刨去一个元素,刨去之后N个数排序需要O(NlogN)。
【在 p********7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题和在文章里面找n个不同words的最小距离很像。算法是每个数组分配一个指针, : 然后取每个指针指向的数组头一个数,排序获得mindistance,每次把最小的数取出, : 换为它所在数组的下一个数,更新排序,更新mindistance。复杂度是 总长度*logN
|
h**6 发帖数: 4160 | 5 这题和文章里找单词的区别在于,不能用你上次说的哈希表与双链表方式来做。
因为文章中可以按照顺序阅读单词,生成双链表。但本题的数据是没有排序的。
【在 p********7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题和在文章里面找n个不同words的最小距离很像。算法是每个数组分配一个指针, : 然后取每个指针指向的数组头一个数,排序获得mindistance,每次把最小的数取出, : 换为它所在数组的下一个数,更新排序,更新mindistance。复杂度是 总长度*logN
|
A*********r 发帖数: 564 | 6 这个历史追述我跟不上了,“不能用你上次说的哈希表与双链表方式来做。”
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题和文章里找单词的区别在于,不能用你上次说的哈希表与双链表方式来做。 : 因为文章中可以按照顺序阅读单词,生成双链表。但本题的数据是没有排序的。
|
d**e 发帖数: 6098 | 7 re...也想知道
【在 A*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个历史追述我跟不上了,“不能用你上次说的哈希表与双链表方式来做。”
|
h**6 发帖数: 4160 | |
A*********r 发帖数: 564 | 9 我猜到你说的可能是这道题,只不过我实在找不出两者之间的任何联系。。
paul说的有联系的是在文章中找N个单词之间的最短距离那道题,不是在文章中找某一
个单词,我理解没错吧?
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://www.mitbbs.com/article_t/JobHunting/31696043.html
|
E********a 发帖数: 124 | 10 大哥, minimum window cover这么经典的题,啥时候你申请版权了。不过贡献题目的
精神还是值得赞扬 |
|
|
h**6 发帖数: 4160 | 11 http://www.mitbbs.com/article_t/JobHunting/31696043.html
以上链接的原题是这么说的:
给一个字符串s1,和一个小串s2,求算法能在s1中找到包含s2里所有字符的最小子串。
比如,
s1 = "ADOBECODEBANC"
s2 = "ABC"
把s1看作一篇文章,A、B、C、D、E都是文中的单词。
那么这道题等价于,在s1这篇文章中,寻找包含s2指定的A、B、C三个单词的最小窗口
。也就跟paul说的那题一样了。 |
r***8 发帖数: 86 | 12 不错,复杂度是不是有点不对,还能再快点吗?:)
【在 p********7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个题和在文章里面找n个不同words的最小距离很像。算法是每个数组分配一个指针, : 然后取每个指针指向的数组头一个数,排序获得mindistance,每次把最小的数取出, : 换为它所在数组的下一个数,更新排序,更新mindistance。复杂度是 总长度*logN
|
r***8 发帖数: 86 | 13 玩笑了,是我想出的一道面试题,肯定早有人想出过这种题。
【在 A*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 版权是啥意思? 你想出来的题,还是是你有独特解法的题? : 这道题让我想起了那个N个数中取出K个数作为子集,使得子集的半径最小的题,可能更 : 复杂一些。。 : 可以用DP, 令 F(k,i,j)表示从前i个序列中取出k的数的最小差值,其中i个序列中取第 : j个数: : F(k,i,j)= min {x in 序列 i-1 } { F(k-1,i-1,x)+abs(A[i-1][x]-A[i][j]) } : 算法复杂度为O(N^2*L), 可以优化为 O(N^2*logL),其中L为最长序列的长度。。
|
r***8 发帖数: 86 | 14 老兄是厉害,一眼就看出来了,两题是一样的:)
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://www.mitbbs.com/article_t/JobHunting/31696043.html : 以上链接的原题是这么说的: : 给一个字符串s1,和一个小串s2,求算法能在s1中找到包含s2里所有字符的最小子串。 : 比如, : s1 = "ADOBECODEBANC" : s2 = "ABC" : 把s1看作一篇文章,A、B、C、D、E都是文中的单词。 : 那么这道题等价于,在s1这篇文章中,寻找包含s2指定的A、B、C三个单词的最小窗口 : 。也就跟paul说的那题一样了。
|
r***8 发帖数: 86 | 15 见笑了,还是仁兄见多识广的。
【在 E********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大哥, minimum window cover这么经典的题,啥时候你申请版权了。不过贡献题目的 : 精神还是值得赞扬
|
p********7 发帖数: 549 | 16 我知道不能用那个方法,所以我这次的方法不是上次那个,我这次用的方法是把这些数
排序,然后更新用binary search,每次更新复杂度是logN, 总复杂度是 总长度×logN
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题和文章里找单词的区别在于,不能用你上次说的哈希表与双链表方式来做。 : 因为文章中可以按照顺序阅读单词,生成双链表。但本题的数据是没有排序的。
|
p********7 发帖数: 549 | 17 第一次排序需要N*logN,但是以后更新每次只需要logN,因为用binary search查找
去之后N个数排序需要O(NlogN)。
【在 A*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 解法很简洁,有点greedy的意思。 : 时间复杂度有点困惑,貌似应该是 总元素个数*NlogN :每一次只刨去一个元素,刨去之后N个数排序需要O(NlogN)。
|
A*********r 发帖数: 564 | 18 嗯,恍然大悟。。
等下一定要去把n个word最小距离的经典题找出来看看,这样以后才能把各种变体题都
联系在一起。。
【在 h**6 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://www.mitbbs.com/article_t/JobHunting/31696043.html : 以上链接的原题是这么说的: : 给一个字符串s1,和一个小串s2,求算法能在s1中找到包含s2里所有字符的最小子串。 : 比如, : s1 = "ADOBECODEBANC" : s2 = "ABC" : 把s1看作一篇文章,A、B、C、D、E都是文中的单词。 : 那么这道题等价于,在s1这篇文章中,寻找包含s2指定的A、B、C三个单词的最小窗口 : 。也就跟paul说的那题一样了。
|
n******h 发帖数: 50 | 19 这还不如做个heap呢。不是一样么。create heap才O(N)。
【在 p********7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一次排序需要N*logN,但是以后更新每次只需要logN,因为用binary search查找 : : 去之后N个数排序需要O(NlogN)。
|
p********7 发帖数: 549 | 20 heap 不合适,因为你要max 和minheap,maxheap更新了,minheap也需要更新,而且删除原来max值不方便
【在 n******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这还不如做个heap呢。不是一样么。create heap才O(N)。
|
|
|
f****g 发帖数: 313 | 21 Yay, the same question! Still thanks a lot to lz!
There are really smart ppls on mitbbs!! |
r***8 发帖数: 86 | 22 大家看这样解法对不对
请把其中的问 题找出来:)
哪位高手能否说出这样找的复杂度是多少
从最短的那个序列中每个数开试
试出有S 个序列,取其中最短DISTANCE的序列既为找的结果
在试的时候,可否这样找
先以刚取出的数为pivot
FOR EACH 剩余的序列
找与pivot 最近的数,
加入已找到的序列,
pivot 调整 为已找到数最大和最小的均值。
【在 r***8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给 N个排好序的正整数一维序列(可看成N个一维数组) : ASSUME 最长序列为 长度为L,最短为S S>=1 : 这些所有正整数没有重复的数 : 现要求从每一个序列中只取一个数组成一个新的N长度序列 : 怎么取才能使新序列中,最大数与最小数的差为最小 : 给出最佳算法,复杂度是多少。
|
A*********r 发帖数: 564 | 23 找出问题来了,每个序列找出来的与pivot最接近的数,并不能保证最后得到的数的最
大与最小之差最小。
反例如下
四个序列分别为 { 2, 20}, {10}, {12, 13}, {1,18}
按照你的算法,10是pivot, 分别从取出的数为 2,10,12,18, 窗口大小为16
但是最优的答案应该是窗口大小为10。
你说得这个对于2个序列的情况适用。
【在 r***8 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大家看这样解法对不对 : 请把其中的问 题找出来:) : 哪位高手能否说出这样找的复杂度是多少 : 从最短的那个序列中每个数开试 : 试出有S 个序列,取其中最短DISTANCE的序列既为找的结果 : 在试的时候,可否这样找 : 先以刚取出的数为pivot : FOR EACH 剩余的序列 : 找与pivot 最近的数, : 加入已找到的序列,
|
r***8 发帖数: 86 | 24 厉害,例子也给得很好。
更正一下,
此法得到的顺序是2,10,12,1
但DISTANCE 11
正确答案应是20,10,12,18
【在 A*********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 找出问题来了,每个序列找出来的与pivot最接近的数,并不能保证最后得到的数的最 : 大与最小之差最小。 : 反例如下 : 四个序列分别为 { 2, 20}, {10}, {12, 13}, {1,18} : 按照你的算法,10是pivot, 分别从取出的数为 2,10,12,18, 窗口大小为16 : 但是最优的答案应该是窗口大小为10。 : 你说得这个对于2个序列的情况适用。
|
m**q 发帖数: 189 | 25 想了想应该一个min heap和一个max值就行了,max值track当前
出现过的所有值中最大的。因为每次从heap中取最小的,所以
只要heap非空,max中记录的当前最大值一定保存在heap中。
删除原来max值不方便
【在 p********7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : heap 不合适,因为你要max 和minheap,maxheap更新了,minheap也需要更新,而且删除原来max值不方便
|
j********x 发帖数: 2330 | 26 I think paul's algorithm has an interesting complexity.
That is, in each iteration, a number if removed and will not be considered
again. So we have exactly sum_i{N_i} iterations, or use N to denote this
number.
Then in each iteration, we need to find the min and max value. This is
actually O(n), where n is the number of arrays.
Overall, we have a O(nN) complexity.
We can improve it by combining two strategies. Remember the problem of find
the minimum window in a longer string that contains all the chars of a
shorter string. It is possible to mimic the solution, using a sliding window
to selecting numbers, where at the same time make sure that all number of
the original n arrays are present in the window.
This can be done, by merging n arrays. This is a O(Nlogn) operation. Then
use the sliding window to find the min window, which is a O(N) operation.
overall, it's O(Nlogn)
This looks to me a sound solution, any comments? |
j********x 发帖数: 2330 | 27 Ah, I got it, the min and max can be found in O(logn) using heap. The
initial heap building is O(n) though. So overall it's O(n) + O(Nlogn) |