我得到了一組 sizen和一個Q輸入串列。每個輸入將洗掉或添加一個數字到這個集合。在每次輸入之后，我應該輸出一組數字的最小絕對差。
約束：
2 <= N <= 10^6
1 <= Q <= 10^6
-10^9 <= set[i] <= 10^9
例子：
輸入：
set = [2, 4, 7]
ADD 6
REMOVE 7
REMOVE 4
ADD 2
輸出：
1
2
4
0
我的任務是使用時間復雜度為O((N Q)log(N Q))或更好的演算法來解決這個問題。
我目前的實作速度不夠快，但是如下：
TreeSet<Integer> tree = new TreeSet<>();
HashMap<Integer, Integer> numberFreq = new HashMap<>();
int dupeCount = 0;
for (int i : set) {
tree.add(i);
if (numberFreq.get(i) > 0) dupeCount ;
numberFreq.put(i, numberFreq.getOrDefault(i, 0) 1);
}
void add(int i) {
if (numberFreq.get(i) > 0) dupeCount ;
numberFreq.put(i, numberFreq.getOrDefault(i, 0) 1);
tree.add(i); // if duplicate nothing gets added anyway
if (dupeCount > 0) Console.write(0);
else {
int smallestBall = ballTree.first();
int absDiff;
int maxAbsDiff = Integer.MAX_VALUE;
while (ballTree.higher(smallestBall) != null) {
absDiff = Math.abs(smallestBall - ballTree.higher(smallestBall));
maxAbsDiff = Math.min(absDiff, maxAbsDiff);
smallestBall = ballTree.higher(smallestBall);
}
Console.write(maxAbsDiff);
}
}
void remove(int i) {
if (numberFreq.get(i) > 0) dupeCount--;
else tree.remove(i);
numberFreq.put(i, numberFreq.get(i) - 1);
if (dupeCount > 0) Console.write(0);
else {
int smallestBall = ballTree.first();
int absDiff;
int maxAbsDiff = Integer.MAX_VALUE;
while (ballTree.higher(smallestBall) != null) {
absDiff = Math.abs(smallestBall - ballTree.higher(smallestBall));
maxAbsDiff = Math.min(absDiff, maxAbsDiff);
smallestBall = ballTree.higher(smallestBall);
}
Console.write(maxAbsDiff);
}
}
我已經嘗試了 2 天了，我很迷茫。
uj5u.com熱心網友回復：
這是一種應該有效的演算法（盡管我不知道這是否是預期的演算法）：
- 對數字串列進行排序
L（如果尚未排序）：L = [2, 4, 7] - 構建一個
D“排序的相鄰絕對差”的對應串列（即排序串列中相鄰對之間的差異，按升序排序）：D = [2, 3] - 對于每個操作...假設操作是 ADD 6，例如。a) 將數字 (6) 插入
L正確（排序的）位置：L = [2, 4, 6, 7]；b）根據您插入它的位置，確定現在已過時的相應相鄰絕對差并將其從中洗掉D（在這種情況下，差異 7-4=3 不再相關并且可以洗掉，因為 4 和 7 不適用更長的相鄰，有 6 個分隔它們）D = [2]：；c) 將兩個新的相鄰絕對差添加到正確（排序的）位置（在這種情況下，6-4=2 和 7-6=1）D = [1, 2, 2]：d) 列印出第一個元素D
如果在第 3 步中遇到移除操作，邏輯類似但略有不同。您將從 中找到并洗掉元素，從洗掉操作L中洗掉的兩個相鄰差異D中洗掉，將新的相關相鄰差異添加到 中D，然后列印 的第一個元素D。
正確性的證明很簡單。最小相鄰絕對差也肯定是最小絕對差，因為兩個不相鄰數字之間的絕對差總是大于或等于按排序順序位于“它們之間”的兩個相鄰數字之間的絕對差。該演算法在每次操作后輸出最小的相鄰絕對差。
對于排序串列資料結構，您有幾個選項。但是由于您希望能夠快速插入、洗掉和讀取有序資料，我建議您使用諸如自平衡二叉樹之類的東西。假設我們使用 AVL 樹。
第 1 步是 O(N log(N))。如果輸入是一個陣列或其他東西，你可以構建一個 AVL 樹；插入 AVL 樹是 log(N)，你必須做 N 次來構建樹。
步驟 2 是 O(N log(N)); L您只需要按升序迭代 AVL 樹，計算相鄰的差異，然后將每個差異插入新的 AVL 樹D（同樣，N 次插入，每個具有 log(N) 復雜度）。
對于單個操作，步驟 3a)、3b)、3c) 和 3d) 都是 O(log(N Q))，因為它們每個都涉及插入、洗掉或從大小為的 AVL 樹中讀取一個或兩個元素< N Q。所以對于單個操作，步驟 3 是 O(log(N Q))。第 3 步在 Q 操作中重復此操作，得到 O(Q log(N Q))。
所以最終演算法的運行時間復雜度是O(N log(N)) O(Q log(N Q))，小于O((N Q) log(N Q))。
編輯：
我剛剛意識到“數字串列”（L）實際上是一個集合（至少，它是根據問題標題，但這可能會產生誤導）。集合不允許重復。但無論哪種方式都很好。每當插入時，只需檢查它是否重復（在確定插入位置之后）。如果它是重復的，則整個操作將變為無操作。這不會改變復雜性。雖然我想這就是 aTreeSet無論如何。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/522660.html
標籤：爪哇排序树放