有沒有辦法創建一個沒有字典的散列表？

我有一個實踐的問題，其中，輸入5個整數元組列表，並且輸出類似的記錄數。例如，在[（1，2，3，4，5），（2,3,4,5,1），（1,3,2,4,5）]中，輸出將是2.

儘管你不應該使用字典，但它來自CLRS，所以你打算使用散列表的概念。

我試過到目前爲止：

一些僞代碼下面我寫道：

它經過列表中的每個指標，比較所有其它指數和旋轉它。

我意識到這是錯誤的，它會運行在O（5n^2），這對於一本關於算法的書來說太高效了。任何建議，我可以做什麼來做到這一點沒有使用字典？

def leftShift(tup, n): 
    if not tup or not n: 
     return tup 
    n %= len(tup) 
    return tup[n:] + tup[:n] 

i = 0 
t = 0 
rotateTuple(L): 
    while i < len(L): 
    if L[i][i] in L[i+1]: 
     while t < 4: 
     .... //This is when I noticed it would fail

的輸出取決於列表中的獨特的元組的數量。元組是一個重複的元素，當它被$ n $旋轉時，它與列表中的另一個元組相同。

來源

2017-02-25 Andrew Raleigh

爲什麼輸出「2」？什麼描述相似性？哈希表在哪裏適合這個？ –

@JonClements：我認爲他意味着平等。但是，[（1,2），（1,2），（2,3），（2,3），（2,3）]'的結果又是什麼？ –

這將是2，因爲有兩個獨特的元組。 @JonClements我編輯了這篇文章。我應該使用哈希表的實現，但不是內置的Python字典。這是一個奇怪的限制，但哈希表將允許使用更少的資源進行更多的比較。 –

字典是一個哈希表，所以不使用字典使用哈希表的唯一方法是實現你自己的，我不會推薦。

您不必將每個元組與每個其他元組進行比較。相反，你可以通過旋轉元組來「歸一化」元組，使得最小的元素在前面，例如， 3,2,6,9,4將被旋轉至2,6,9,4,3。如果列表不止一次包含最小元素，則必須找到最小元素的所有位置，並按列表的自然順序獲得「最小」的旋轉。 1,2,3,4,1歸一化爲1,1,2,3,4和1,3,1,2至1,2,1,3。你可以將標準化的元組放入O（n）中的一組「唯一」元組中。

lsts = [(1, 2, 3, 4, 5), (2, 3, 4, 5, 1), (1, 3, 2, 4, 5)] 
unique = set(map(normalize, lsts)) # has length 2

這可以說，雖然，一個set只是一個dict沒有價值。在這種情況下，您可以對歸一化元組列表進行排序，並檢查O（nlogn + n）中的重複項。

srtd = sorted(map(normalize, lsts)) 
n = len(lsts) - sum(srtd[i-1] == srtd[i] for i in range(1, len(srtd))) # 2

來源

2017-02-25 17:26:09

「key = lambda x」初始化字典。有沒有辦法在不使用字典的情況下獲得相同的結果。在此期間，我將嘗試使用鏈接列表來實現您的工作。 –

@AndrewRaleigh我不知道'min'的'key'參數創建了一個'dict';畢竟，每個密鑰只需要一次（除了''''鍵''''排序'）。無論如何，請參閱我的編輯，以查找沒有'key'的'min'（實際上沒有'min'）。 –

嘿，我注意到它不適用於（3,9,15,2,1）和（15,2,1,3,9），任何想法爲什麼不呢？ –

有沒有辦法創建一個沒有字典的散列表？

回答

相關問題