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 的大作中提到】
: 给 N个排好序的正整数一维序列（可看成N个一维数组）
: ASSUME 最长序列为 长度为L，最短为S S>=1
: 这些所有正整数没有重复的数
: 现要求从每一个序列中只取一个数组成一个新的N长度序列
: 怎么取才能使新序列中，最大数与最小数的差为最小
: 给出最佳算法，复杂度是多少。
|
A*********r
发帖数: 564 | 4 解法很简洁，有点greedy的意思。
时间复杂度有点困惑，貌似应该是 总元素个数*NlogN ：每一次只刨去一个元素，刨去之后N个数排序需要O（NlogN）。
【在 p********7 的大作中提到】
: 这个题和在文章里面找n个不同words的最小距离很像。算法是每个数组分配一个指针，
: 然后取每个指针指向的数组头一个数，排序获得mindistance，每次把最小的数取出，
: 换为它所在数组的下一个数，更新排序，更新mindistance。复杂度是 总长度*logN
|
h**6
发帖数: 4160 | 5 这题和文章里找单词的区别在于，不能用你上次说的哈希表与双链表方式来做。
因为文章中可以按照顺序阅读单词，生成双链表。但本题的数据是没有排序的。
【在 p********7 的大作中提到】
: 这个题和在文章里面找n个不同words的最小距离很像。算法是每个数组分配一个指针，
: 然后取每个指针指向的数组头一个数，排序获得mindistance，每次把最小的数取出，
: 换为它所在数组的下一个数，更新排序，更新mindistance。复杂度是 总长度*logN
|
A*********r
发帖数: 564 | 6 这个历史追述我跟不上了，“不能用你上次说的哈希表与双链表方式来做。”
【在 h**6 的大作中提到】
: 这题和文章里找单词的区别在于，不能用你上次说的哈希表与双链表方式来做。
: 因为文章中可以按照顺序阅读单词，生成双链表。但本题的数据是没有排序的。
|
d**e
发帖数: 6098 | 7 re...也想知道
【在 A*********r 的大作中提到】
: 这个历史追述我跟不上了，“不能用你上次说的哈希表与双链表方式来做。”
|
h**6
发帖数: 4160 | |
A*********r
发帖数: 564 | 9 我猜到你说的可能是这道题，只不过我实在找不出两者之间的任何联系。。
paul说的有联系的是在文章中找N个单词之间的最短距离那道题，不是在文章中找某一
个单词，我理解没错吧？
【在 h**6 的大作中提到】
: 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 的大作中提到】
: 这个题和在文章里面找n个不同words的最小距离很像。算法是每个数组分配一个指针，
: 然后取每个指针指向的数组头一个数，排序获得mindistance，每次把最小的数取出，
: 换为它所在数组的下一个数，更新排序，更新mindistance。复杂度是 总长度*logN
|
r***8
发帖数: 86 | 13 玩笑了，是我想出的一道面试题，肯定早有人想出过这种题。
【在 A*********r 的大作中提到】
: 版权是啥意思？ 你想出来的题，还是是你有独特解法的题？
: 这道题让我想起了那个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 的大作中提到】
: 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 的大作中提到】
: 大哥， minimum window cover这么经典的题，啥时候你申请版权了。不过贡献题目的
: 精神还是值得赞扬
|
p********7
发帖数: 549 | 16 我知道不能用那个方法，所以我这次的方法不是上次那个，我这次用的方法是把这些数
排序，然后更新用binary search，每次更新复杂度是logN, 总复杂度是 总长度×logN
【在 h**6 的大作中提到】
: 这题和文章里找单词的区别在于，不能用你上次说的哈希表与双链表方式来做。
: 因为文章中可以按照顺序阅读单词，生成双链表。但本题的数据是没有排序的。
|
p********7
发帖数: 549 | 17 第一次排序需要N*logN，但是以后更新每次只需要logN，因为用binary search查找
去之后N个数排序需要O（NlogN）。
【在 A*********r 的大作中提到】
: 解法很简洁，有点greedy的意思。
: 时间复杂度有点困惑，貌似应该是 总元素个数*NlogN ：每一次只刨去一个元素，刨去之后N个数排序需要O（NlogN）。
|
A*********r
发帖数: 564 | 18 嗯，恍然大悟。。
等下一定要去把n个word最小距离的经典题找出来看看，这样以后才能把各种变体题都
联系在一起。。
【在 h**6 的大作中提到】
: 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 的大作中提到】
: 第一次排序需要N*logN，但是以后更新每次只需要logN，因为用binary search查找
:
: 去之后N个数排序需要O（NlogN）。
|
p********7
发帖数: 549 | 20 heap 不合适，因为你要max 和minheap，maxheap更新了，minheap也需要更新，而且删除原来max值不方便
【在 n******h 的大作中提到】
: 这还不如做个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 的大作中提到】
: 给 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 的大作中提到】
: 大家看这样解法对不对
: 请把其中的问 题找出来：）
: 哪位高手能否说出这样找的复杂度是多少
: 从最短的那个序列中每个数开试
: 试出有S 个序列，取其中最短DISTANCE的序列既为找的结果
: 在试的时候，可否这样找
: 先以刚取出的数为pivot
: FOR EACH 剩余的序列
: 找与pivot 最近的数，
: 加入已找到的序列，
|
r***8
发帖数: 86 | 24 厉害，例子也给得很好。
更正一下，
此法得到的顺序是2，10，12，1
但DISTANCE 11
正确答案应是20,10,12,18
【在 A*********r 的大作中提到】
: 找出问题来了，每个序列找出来的与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 的大作中提到】
: 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) |
