Given two arrays A [1..n] and B[1..m], find the smallest window in A that contains all elements of B. That is, find a pair <l,k> such that A[l..k] contains B[1..m] For example, given A = 3,1,5,7,3,5,2 and B = 5,3 then the smallest window is [3,5].
阅微客栈 » 头脑风暴
Amazon面试题 - 找最短的cover
(10 posts)-
发布于 1 年 之前 #
-
szuxjq
Member像是匹配字符串。举例和描述有点不同？
发布于 1 年 之前 # -
smallest window is [3, 5] means from 3rd-5th, that is 5, 7, 3, cover B=5,3
发布于 1 年 之前 # -
szuxjq
Member应该有序的吧？否则应该是第五个到第六个才对啊？
发布于 1 年 之前 # -
stephen
MemberO(nlogm+mlogm)
整个算法只对A数组进行一次扫描
维护m个变量h_1,h_2,...,h_m，h_i表示最靠近当前扫描点的一个序列B_1,B_2,...,B_i的起始位置B_1。
同时保存最小的窗口s信息。
在整个扫描的过程中不断的更新这些变量。
假设在扫描到A_j位置时碰到B_i，这时比较h_{i-1}和h_i，如果h_{i-1}<h_i，那么更新h_i=h_{i-1}。
当碰到B_m时计算出j-h_m，和已保存的窗口信息s比较，如果更小，那么更新s的信息。
这样就能找出最小的窗口了。
然后计算时间复杂度，整个扫描过程O(n),但是每次取出一个数需要判断它是否是B中的数，所以需要logm
的时间来二分查找，因为B开始没有排序过，所以需要格外的mlogm时间排序。发布于 1 年 之前 # -
stephen
Memberwk....怎么刷出来这么多，你得blog有问题啊
发布于 1 年 之前 # -
fung
Member先读出B1，在A中搜索B1，记下其位置loc1。
读B2，在Aloc1开始向后，
扫描Aloc1后面的元素，
扫描发现B1，则记下其位置loc2；
若发现了B2，则记下其位置loc3，停止这次扫描。
...
读Bi，
扫描Aloci后面元素，
发现有B1，记下其位置'，发现B2，记下其位置'....发现Bj，记下其位置'locj
发现Bi{
若j<i-1;清空上面的B1～Bj的位置'，记下Bi的位置；停止扫描；记下其在A的位置locj}
读Bi+1
扫描从Alocj+1开始...发布于 8 月 之前 # -
fung
Member补上：
倒数第三行：
否则(即j=i-1)，将位置loc1～loci-1替换成 位置'(即后面得到的新地址)；发布于 8 月 之前 # -
LCS ＋ 标记起始位置
发布于 7 月 之前 # -
Yuanyuan
Member额滴神呀~~~~
看着有点像数列，
嗯·····sorry ,i don't know ...发布于 5 月 之前 #
回复
你必须 登录 后发帖。