編程和數據結構

-4

推薦用於表示整數的子集S從1到n的數據結構。對集合S的以下操作將在恆定時間內執行（獨立於S的基數）。您可能會認爲數據結構已被適當初始化。編程和數據結構

（i）中。 MEMBER（X）：

檢查X是否是在該組S或不

（ii）中。 FIND-ONE（S）：若S不爲空，返回集合S的一個元素（任意元素都可以）

（III）。 ADD（X）：添加整數X到集合S

（ⅳ）。刪除（X）：從S中刪除整數X.

我的分析： - 我認爲哈希表在這裏可以正常工作，但哈希表如何工作FIND-ONES（S）操作。因爲我可能需要掃描整個桌子都在尋找目前的元素。

來源

2017-10-04 rahul sharma

什麼是SS？和S一樣嗎？ –

這是錯字，我現在糾正它。 –

哈希表的工作，但你需要考慮的具體實施。如果您使用compact version from Python 3.6，您可以通過檢查entries名單在固定時間內進行FIND-ONEs。

例如，詞典：

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

如下表示：

indices = [None, 1, None, None, None, 0, None, 2] 
entries = [[-9092791511155847987, 'timmy', 'red'], 
      [-8522787127447073495, 'barry', 'green'], 
      [-6480567542315338377, 'guido', 'blue']]

來源

2017-10-04 21:04:17 user3080953

你可以只使用一個普通的HashSet這在java中。在FIND-ONE(S)的情況下，您要做的是，請致電isEmpty()。如果返回false，則使用內置的迭代器，並獲取迭代器返回的第一個值。

來源

2017-10-05 17:57:25

編程和數據結構

回答

相關問題