在陣列中查找範圍

我一直在努力尋找出現在工作中的以下（有趣？）問題的最佳解決方案：最終，我解決了一個足夠好的解決方案，但我想知道是否有更好的解決方案一。在陣列中查找範圍

讓a ... a _n是一個字符串數組。

令S 內容S _ķ是一個無序的字符串列表，所有的人也數組的成員。

任務是找到a中s覆蓋的最小索引範圍eleements集。例如，如果a = [「x」，「y」，「a」，「f」，「c」]和s = {「c」，「y」，「f」}，那麼答案（1; 1），（3; 4），假設數組從零開始索引。

a通常相當大（數十萬個元素），而s相對較小，通常爲長度（s）<log（長度（a））。

所以問題是：你能爲這個問題找到一個省時的算法嗎？（空間效率不是合理限制內的問題。）

只是一個快速但重要的更新：我需要使用不同的s值執行此操作，但同一個a很多。所以基於a的預計算是允許的，實際上它是唯一的方法。

來源

2011-03-02 biziclop

你的意思是（S0：A4），（S1：A1），（S2：F4）？ – Muggen 2011-03-02 21:24:08

不，我的意思是「c」和「f」在「a」中是連續的，並且它們跨越了指數3-4之間的範圍，「y」是獨立的，所以它只是1-1的範圍。 – biziclop 2011-03-02 21:27:56

好吧，我現在看到。謝謝。 – Muggen 2011-03-02 21:29:42

生成哈希表H(a)從元件映射到索引：a_X->x在O(n)時間和空間。然後查看每個s _yH(a)（在O(1)時間平均爲O(k)爲s）並跟蹤範圍。爲此，您可以使用排序爲min_index的pair(min_index, max_index)數組，並執行二進制搜索以找到範圍或應插入新的1元素範圍的位置。
總體而言，上述解決方案需要O(n + k + k * log(nb_ranges))時間和O(n + nb_ranges)空間。

來源

2011-03-02 23:06:13

我想你可以把S的元素放入一個集合或散列表中，任何接近O（1）的東西來檢查成員資格。然後，只需在A上進行線性掃描，並帶有一個標記，以確定您當前是否覆蓋S中的元素以及該封面的起始位置。應該是O（n + k）。

來源

2011-03-02 21:26:36 dgtized

嗯，這是我最初的想法，事實證明它有點慢。 – biziclop 2011-03-02 21:32:55

這是你想要的，用Python編寫的：

def flattened(indexes): 
    s, rest = indexes[0], indexes[1:] 
    result = (s, s) 
    for e in rest: 
     if e == result[1] + 1: 
      result = (result[0], e) 
     else: 
      yield result 
      result = (e, e) 
    yield result 

a = ["x", "y", "a", "f", "c"] 
s = ["c", "y", "f"] 

# Create lookup table of ai to index in a 
src_indexes = dict((key, i) for i, key in enumerate(a)) 

# Create sorted list of all indexes into a 
raw_dst_indexes = sorted(src_indexes[key] for key in s) 

# Convert sorted list of indexes into an array of ranges 
dst_indexes = [r for r in flattened(raw_dst_indexes)] 

print dst_indexes

來源

2011-07-10 20:25:16 hughdbrown

在陣列中查找範圍

回答

相關問題