例如：
T = [b, c, b, b, a, c] #each element represents questions related to topics a, b, c
我想要的是確保沒有來自同一主題的 2 個問題彼此相鄰。（見 T 其中 b，b 彼此相鄰）
所以我想重新排列 T 使得屬于同一主題的兩個問題都不相鄰，即 Tnew = [b, c, b, a, b, c]
但條件是我們必須在線性時間內完成，即 O(n) 或 (n) 的 Big-O
The algorithm that I thought of:
1)Create a dict or map to hold the occurrence of each topics:
a --> 1
b --> 3
c --> 2
2) Now based on the counts we can create new array such that:
A = [a, b, b, b, c, c]
3) Now perform unsorting of Array which I believe runs in O(n).
(unsorting is basically find midpoint and then merge the elements alternately from each half.
有人可以幫我設計一個偽代碼或演算法，它可以在任何具有 k 個主題的輸入上做得更好嗎？
這是我為考試而練習的一個隨機問題。
uj5u.com熱心網友回復：
有一種時間復雜度的線性方法，O(log c * n)其中c是唯一項的數量，n是項的總數。
它的作業原理如下：
- 創建專案的頻率表。這只是一個元組串列，它告訴每個專案有多少可用。讓我們將串列中的元組存盤為
(quantity, item). 這一步是O(n)。您可以collections.Counter在 pythoncollections.defaultdict(int)或 vanilla中使用dict。 - Heapify 最大堆中的元組串列。這可以在
O(n). 該堆的最前面是數量最多的專案。您可以heapq在 python 中使用模塊。我們稱之為堆hp。 - 有一個名為 的結果串列
res。 - 現在運行一個回圈
while len(hp) > 0:并執行以下操作：
- 從堆中彈出 2 個最大的元素。
O(log c)手術。 - 從每個添加一個到
res. 確保正確處理邊緣情況（如果有）。 - 減少這兩個專案的數量。如果他們
quantity > 0把他們推回堆上。O(log c)手術。
最后，您可以以一個沒有對等項進行交織的專案結束。如果一個專案的數量大于所有其他專案的數量之和，就會發生這種情況。但是沒有辦法解決這個問題。您的輸入資料必須遵守此條件。
關于時間復雜度的最后一點說明：如果唯一專案的數量是恒定的，我們可以log c從時間復雜度中洗掉該因素并認為它是線性的。這主要是我們如何定義事物的一個案例。
uj5u.com熱心網友回復：
這是 O(n) 解決方案（部分靈感來自@user1984 的回答）：
想象一下，您知道要插入每個元素的數量，并且已經對這些數量進行了排序。假設我們隨后決定通過逐步交織元素組來構建解決方案。我們從頻率最低的一組元素 G0 開始。然后，我們選取??下一個最受歡迎的組 G1，并將這些值交織到我們現有的串列中。
如果我們以這種方式繼續下去，我們可以遵守一些規則：
- 如果當前組 G 的元素比所有較小組的總和加一還多，則：
- 結果將有 G 的元素彼此相鄰
- 無論其先前狀態如何，較小組中的任何元素都不會彼此相鄰（組間或組內）
- 否則
- 結果將沒有 G 的元素彼此相鄰
- 無論如何，如果定位得當，G 包含足夠的元素來分隔下一個最小組 G-1 的各個元素。
考慮到這一點，我們可以（遞回地）看到，只要我們改變交錯以重疊任何突出的鄰居違規，我們就可以保證只要 G 的元素少于較小的組加起來的兩個元素，整體結果絕對會沒有任何鄰居違規行為。
當然，我上面概述的用于計算它的邏輯會帶來一些性能問題，因此我們將以稍微不同但等效的方式計算相同的結果。相反，我們將首先插入最大的組，然后以較小的方式作業。
首先，創建一個頻率表。你需要形成一個item: quantity映射，所以就像collections.Counter()在 python 中一樣。這需要O(N)時間。
接下來，按頻率對該映射進行排序。這可以O(N)使用計數排序及時完成，因為所有元素都是整數。注意有c元素，但是c <= N，所以O(c)是O(N)。
之后，構建一個長度鏈表N，節點值從[0, N)（升序）開始。這將幫助我們跟蹤接下來要寫入哪些索引。
對于我們有序映射中的每個專案，從 0 迭代到相關的計數（不包括）。每次迭代，從鏈表中移除當前元素（（重新）從頭部開始），并在鏈表中向前遍歷兩個節點。將專案/編號插入目標陣列中每個已洗掉節點的索引處。這需要O(N)時間，因為我們每個專案遍歷約 2k 個節點（k在組大小中），并且所有組的組合大小為N，所以2N遍歷。每次移除都可以及時執行O(1)，所以O(N)對于遍歷移除。
所以總而言之，這需要O(N)時間，利用鏈表、哈希表（或某種 O(1) 訪問映射）和計數排序。
uj5u.com熱心網友回復：
集合模塊可以提供幫助。使用Counter可以讓您在 O(n) 時間內出現每個問題的次數。將它們轉換為 a 中的迭代器deque將允許您按順序交錯問題，但您需要按出現的遞減順序處理它們。按頻率順序獲取計數器通常需要一個排序，即 O(nLogn)，但您可以使用鴿子洞方法在 O(n) 時間內按共同頻率對迭代器進行分組，然后以相反的順序遍歷組頻率。不同頻率的最大數量是已知的，并且將小于或等于 √(0.25 2n)-0.5，它小于 O(n)。
最多會有n迭代器，因此構建雙端佇列將 <= O(n)。遍歷迭代器直到用盡最多需要 2n 次迭代：
T= ['b', 'c', 'b', 'b', 'a', 'c']
from collections import Counter,deque
from itertools import repeat
result = []
counts = Counter(T) # count occurrences O(n)
common = [[] for _ in range(max(counts.values()))] # frequency groups
for t,n in counts.items():
common[n-1].append(repeat(t,n)) # iterators by freq.
Q = deque(iq for cq in reversed(common) for iq in cq) # queue iterators
while Q: # 2n iterations or less
iq = Q.popleft() # O(1) - extract first iterator
q = next(iq,None) # O(1) - next question
if not q: continue # - exhausted, removed from deque
result.append(q) # O(1) - add question to result
Q.insert(1,iq) # O(1) - put back iterator as 2nd
print(result)
['b', 'c', 'b', 'c', 'b', 'a']
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422799.html
標籤：
上一篇：計算簡單多邊形的面積