我有一個大的唯一數字排序陣列。我確實想將其拆分為具有唯一值的n較小的不相交的排序陣列。例如，我有一個陣列[1, 2, 3, 4, 5, 6, 7, 8, 9]，我正在尋找的演算法給出以下結果之一（n=3）：
[1, 4, 7], [5, 6, 9], [2, 3, 8][3, 8, 9], [1, 5, 7], [2, 4, 6][3, 4, 7], [1, 5, 8], [2, 6, 9]， 等等
為什么需要它：我有一個非常大的陣列（大約 10 億個值），我需要在模擬網路中的節點之間隨機分配值，它們一起計算一些聚合值。如果它們具有排序值，它們的作業效率會更高。由于我正在測驗這個系統，我需要使用不同數量的節點、網路拓撲等多次運行模擬。顯然，在這里簡單地將資料分成幾個連續的塊是不合適的。
uj5u.com熱心網友回復：
創建n較小的陣列和n索引陣列。每個小陣列都有一個索引；它們都被初始化為零。遍歷大的排序陣列，在??每一步選擇一個小陣列來放入值。如果小陣列已經“滿”（它的索引已經等于陣列的長度），則選擇下一個尚未滿的小陣列。將大陣列中的值插入到小陣列索引的當前值處，然后遞增索引。
這將需要一個快速的亂數生成器，也許還需要一個巧妙的方法將完整的子陣列從旋轉中取出，但它在大型排序陣列中是線性的，不需要排序。
在 Java 中，二維陣列是陣列的陣列，我們可以利用它來動態更改每行指向的子陣列。這里的想法是這subarrays是一個包含所有子陣列的陣列，對它們的參考永遠不會改變，而是candidate從對所有子陣列的參考開始，然后逐漸調整自身，以便只參考仍未滿的陣列。
int[][] splitSorted(int[] array, int n) {
if (array.length % n != 0) {
throw new IllegalArgumentException(
n " does not divide " array.length " evenly");
}
int size = array.length / n; // size of each subarray
int[][] subarrays = new int[n][size];
int[][] candidate = Arrays.copyOf(subarrays, subarrays.length);
int[] index = new int[n];
Random rand = new Random();
for (int i : array) {
int which = rand.nextInt(n);
candidate[which][index[which]] = i; // insert into a subarray
index[which];
if (index[which] == size) { // one has maxed out
--n; // remove it from consideration
candidate[which] = candidate[n];
index[which] = index[n];
}
}
return subarrays;
}
當一個陣列已滿時，我們將末尾的那個交換candidate到它的位置，以便第一行包含我們仍在嘗試填充的那些。請注意，它candidate完全失去了對填充陣列的跟蹤。這很好，因為它們仍然被 參考subarrays，而永遠不會改變。（我們通過在創建時candidate使用淺拷貝來避免它的別名。）我們還必須交換我們正在交換的陣列的索引。Arrays::copyOfcandidate
另請注意，進行交換的兩條線上的which可能n是相同的。在這種if情況下可以避免設定它們，但設定它們是多余的，所以我更喜歡讓代碼更簡單。n遞減，所以下一次回圈時，我們將選擇一個較小范圍內的亂數；僅考慮仍需要填充的陣列。最后，我們回傳一個包含所有填充子陣列的陣列。
應該很清楚，但我要強調的是，因為我們將原始大型排序陣列中的每個值放入一個且只有一個子陣列中，并且因為我們將它們按順序放置在那里，所以原始陣列的唯一性和排序約束將是維護在子陣列上。
uj5u.com熱心網友回復：
您可以打亂串列，拆分為塊并對塊進行排序。例如（Python 中的解決方案）：
import random
n = 3
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
random.shuffle(lst)
for i in range(0, len(lst), n):
print(sorted(lst[i : i n]))
印刷：
[1, 2, 8]
[3, 6, 9]
[4, 5, 7]
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424340.html
上一篇：尋找減少分數的最有效方法
下一篇：獲取陣列前綴中的主導元素